Oxidation of methionine residues to methionine sulfoxide can lead to inactivation of proteins. Methionine sulfoxide reductase (MsrA) has been known for a long time, and its repairing function well characterized. Here we identify a new methionine sulfoxide reductase, which we referred to as MsrB, the gene of which is present in genomes of eubacteria, archaebacteria, and eucaryotes. The msrA and msrB genes exhibit no sequence similarity and, in some genomes, are fused. The Escherichia coli MsrB protein (currently predicted to be encoded by an open reading frame of unknown function named yeaA) was used for genetic, enzymatic, and mass spectrometric investigations. Our in vivo study revealed that msrB is required for cadmium resistance of E. coli, a carcinogenic compound that induces oxidative stress. Our in vitro studies, showed that (i) MsrB and MsrA enzymes reduce free methionine sulfoxide with turn-over rates of 0.6 min(-1) and 20 min(-1), respectively, (ii) MsrA and MsrB act on oxidized calmodulin, each by repairing four to six of the eight methionine sulfoxide residues initially present, and (iii) simultaneous action of both MsrA and MsrB allowed full reduction of oxidized calmodulin. A possibility is that these two ubiquitous methionine sulfoxide reductases exhibit different substrate specificity.