Here we report that the Salmonella Typhimurium NatB (SeNatB) protein N-terminal acetyltransferase acetylated the N-terminal methionine of the nucleoid-associated HU proteins. Our findings were supported by an in vitro analysis of acetylation of the HUα and HUβ proteins and lysine-null (K-null) variants, and by an in vivo analysis of the effect of acetylation on HU-mediated transcriptional regulation of a known target of HU, the hilA promoter. SeNatB did not acetylate the initiating methionines of HU proteins that were oxidized to methionine sulfoxide, but the reduction of these methionine sulfoxide residues restored the acetylation of HU proteins by SeNatB. These results demonstrate that the SeHU proteins are bona fide substrates for the methionine sulfoxide reductases MsrA and MsrB. Finally, we showed that the Bacillus subtilis acetyltransferase, YfmK, is a functional homolog of SeNatB, and that BsYfmK acetylates the Nα amino group of the initiating methionine of the B. subtilis HU protein (HBsu).