Mycoplasma genitalium is the smallest self-replicating microorganism and is implicated in human diseases, including urogenital and respiratory infections and arthritides. M. genitalium colonizes host cells primarily through adherence mechanisms mediated by a network of surface-associated membrane proteins, including adhesins and cytadherence-related proteins. In this paper, we show that cytadherence in M. genitalium is affected by an unrelated protein known as peptide methionine sulfoxide reductase (MsrA), an antioxidant repair enzyme that catalyzes the reduction of methionine sulfoxide [Met(O)] residues in proteins to methionine. An msrA disruption mutant of M. genitalium, constructed through homologous recombination, displayed markedly reduced adherence to sheep erythrocytes. In addition, the msrA mutant was incapable of growing in hamsters and exhibited hypersensitivity to hydrogen peroxide when compared to wild-type virulent M. genitalium. These results indicate that MsrA plays an important role in M. genitalium pathogenicity, possibly by protecting mycoplasma protein structures from oxidative damage or through alternate virulence-related pathways.