Mycoplasma genitalium is a human pathogen that mediates cell adhesion by a complex structure known as the attachment organelle. This structure is composed of cytadhesins and cytadherence-associated proteins, but few data are available about the specific role of these proteins in M. genitalium cytadherence. We have deleted by homologous recombination the mg191 and mg192 genes from the MgPa operon encoding the P140 and P110 cytadhesins. Molecular characterization of these mutants has revealed a reciprocal posttranslational stabilization between the two proteins. Loss of either P140 or P110 yields a hemadsorption-negative phenotype and correlates with decreased or increased levels of cytoskeleton-related proteins MG386 and DnaK, respectively. Scanning electron microscopy analysis reveals the absolute requirement of P140 and P110 for the proper development of the attachment organelle. The phenotype described for these mutants resembles that of the spontaneous class I and class II cytadherence-negative mutants [G. R. Mernaugh, S. F. Dallo, S. C. Holt, and J. B. Baseman, Clin. Infect. Dis. 17(Suppl. 1):S69-S78, 1993], whose genetic basis remained undetermined until now. Complementation assays and sequencing analysis demonstrate that class I and class II mutants are the consequence of large deletions affecting the mg192 and mg191-mg192 genes, respectively. These deletions originated from single-recombination events involving sequences of the MgPa operon and the MgPa island located immediately downstream. We also demonstrate the translocation of MgPa sequences to a particular MgPa island by double-crossover events. Based on these observations, we propose that in addition to being a source of antigenic variation, MgPa islands could be also involved in a general phase variation mechanism switching on and off, in a reversible or irreversible way, the adhesion properties of M. genitalium.