The reduction of methionine sulfoxide (MetO) is mediated by methionine sulfoxide reductases (Msr). The MsrA and MsrB families can reduce free MetO and MetO within a peptide or protein context. This process is stereospecific with the S- and R-forms of MetO repaired by MsrA and MsrB, respectively. Cell extracts from an MsrA(-)B(-) knockout of Escherichia coli have several remaining Msr activities. This study has identified an enzyme specific for the free form of Met-(R)-O, fRMsr, through proteomic analysis. The recombinant enzyme exhibits the same substrate specificity and is as active as MsrA family members. E. coli fRMsr is, however, 100- to 1,000-fold more active than non-selenocysteine-containing MsrB enzymes for free Met-(R)-O. The crystal structure of E. coli fRMsr was previously determined, but no known function was assigned. Thus, the function of this protein has now been determined. The structural similarity of the E. coli and yeast proteins suggests that most fRMsrs use three cysteine residues for catalysis and the formation of a disulfide bond to enclose a small active site cavity. This latter feature is most likely a key determinant of substrate specificity. Moreover, E. coli fRMsr is the first GAF domain family member to show enzymatic activity. Other GAF domain proteins substitute the Cys residues and others to specifically bind cyclic nucleotides, chromophores, and many other ligands for signal potentiation. Therefore, Met-(R)-O may represent a signaling molecule in response to oxidative stress and nutrients via the TOR pathway in some organisms.