Selenoprotein R (SelR) is a mammalian selenocysteine-containing protein with no known function. Here we report that cysteine homologs of SelR are present in all organisms except certain parasites and hyperthermophiles, and this pattern of occurrence closely matches that of only one protein, peptide methionine sulfoxide reductase (MsrA). Moreover, in several genomes, SelR and MsrA genes are fused or clustered, and their expression patterns suggest a role of both proteins in protection against oxidative stress. Consistent with these computational screens, growth of Saccharomyces cerevisiae SelR and MsrA mutant strains was inhibited, and the strain lacking both genes could not grow, in the presence of H₂O₂ and methionine sulfoxide. We found that the cysteine mutant of mouse SelR, as well as the Drosophila SelR homolog, contained zinc and reduced methionine-R-sulfoxide, but not methionine-S-sulfoxide, in in vitro assays, a function that is both distinct and complementary to the stereo-specific activity of MsrA. These findings identify a function of the conserved SelR enzyme family, define a pathway of methionine sulfoxide reduction, reveal a case of convergent evolution of similar function in structurally distinct enzymes, and suggest a previously uncharacterized redox regulatory role of selenium in mammals.