Mycoplasmas are the smallest known microorganisms, with drastically reduced genome sizes. One of the essential biochemical pathways lost in mycoplasmas is methylation-mediated DNA repair (MMR), which is responsible for correction of base substitutions, insertions, and deletions in both bacteria and higher organisms. We found that the histone-like protein encoded by the himA/hup_2 gene of Mycoplasma gallisepticum (mgHU) recognizes typical MMR substrates, in contrast to homologues from other species. The recognition of substitution mismatches is sequence-dependent, with affinities decreasing in the following order CC > CT = TT > AA = AC. Insertions or deletions of one nucleotide are also specifically recognized with the following sequence-dependent preference A = T > C. One-nucleotide lesions involving guanine are bound only weakly, and this binding is indistinguishable from binding to intact DNA. Although mgHU is dissimilar to Escherichia coli HU, expression in a slow-growing hupAB E. coli strain restores wild-type growth. The results indicate that mgHU executes all essential functions of bacterial architectural proteins. The origin and the possible role of enhanced specificity for typical MMR substrates are discussed.