Mycobacterium tuberculosis and Mycobacterium bovis bacillus Calmette-Guérin produce a heparin-binding hemagglutinin adhesin (HBHA) required for extrapulmonary dissemination and a laminin-binding protein (LBP) involved in cytoadherence through laminin recognition. These adhesins bear posttranslational modifications that are not present when the proteins are produced in a recombinant (r) form in Escherichia coli. Mass spectrometry analysis of HBHA revealed that the posttranslational modifications are borne by the C-terminal moiety, which comprises the heparin-binding domain made of repeated lysine-rich motifs. Amino acid sequencing showed that these modifications consist of mono- and dimethyllysines within these motifs. The methyllysine-containing repeats were recognized by mAb 4057D2 and were also detected in LBP, which is equally recognized by mAb 4057D2. This Ab does not recognize the recombinant forms of these proteins. However, when rHBHA and rLBP were subjected to NaBH(4) and formalin treatment to induce lysine methylation, reactivity with mAb 4057D2 was recovered. Methylated rHBHA displayed enhanced resistance to proteolysis compared with rHBHA, as previously observed for native HBHA. S-adenosylmethionine-dependent HBHA methyltransferase activity was detected in the cell-wall fractions of M. bovis bacillus Calmette-Guérin and of Mycobacterium smegmatis, a species that produces LBP but naturally lacks hbhA, suggesting that the same enzyme(s) methylate(s) both LBP and HBHA. This hypothesis was confirmed by the fact that HBHA produced by recombinant M. smegmatis was also methylated. These results show that mycobacteria use enzymatic methylation of lysines to ensure greater stability of their adhesins.