Controlling iron homeostasis is crucial for all aerobically grown living cells that are exposed to oxidative damage by reactive oxygen species (ROS), as free iron increases the production of ROS. Methionine sulfoxide reductases (Msr) are key enzymes in repairing ROS-mediated damage to proteins, as they reduce oxidized methionine (MetSO) residues to methionine. E. coli synthesizes two Msr, A and B, which exhibit substrate diastereospecificity. The bacterial iron-responsive small RNA (sRNA) RyhB controls iron metabolism by modulating intracellular iron usage. We show in this paper that RyhB is a direct regulator of the msrB gene that encodes the MsrB enzyme. RyhB down-regulates msrB transcripts along with Hfq and RNaseE proteins since mutations in the ryhB, fur, hfq, or RNaseE-encoded genes resulted in iron-insensitive expression of msrB. Our results show that RyhB binds to two sequences within the short 5'UTR of msrB mRNA as identified by reverse transcriptase and RNase and lead (II) protection assays. Toeprinting analysis shows that RyhB pairing to msrB mRNA prevents efficient ribosome binding and thereby inhibits translation initiation. In vivo site directed-mutagenesis experiments in the msrB 5'UTR region indicate that both RyhB-pairing sites are required to decrease msrB expression. Thus, this study suggests a novel mechanism of translational regulation where a same sRNA can basepair to two different locations within the same mRNA species. In contrast, expression of msrA is not influenced by changes in iron levels.