Campylobacter jejuni is a bacterial pathogen that is generally acquired as a zoonotic infection from poultry and animals. Adhesion of C. jejuni to human colorectal epithelial cells is weakened after loss of its cj0588 gene. The Cj0588 protein belongs to the type I group of TlyA (TlyAI) enzymes, which 2′-O-methylate nucleotide C1920 in 23S rRNA. Slightly longer TlyAII versions of the methyltransferase are found in actinobacterial species including Mycobacterium tuberculosis, and methylate not only C1920 but also nucleotide C1409 in 16S rRNA. Loss of TlyA function attenuates virulence of both M. tuberculosis and C. jejuni. We show here that the traits impaired in C. jejuni null strains can be rescued by complementation not only with the original cj0588 (tlyAI) but also with a mycobacterial tlyAII gene. There are, however, significant differences in the recombinant phenotypes. While cj0588 restores motility, biofilm formation, adhesion to and invasion of human epithelial cells and stimulation of IL-8 production in a C. jejuni null strain, several of these properties are further enhanced by the mycobacterial tlyAII gene, in some cases to twice the original wild-type level. These findings strongly suggest that subtle changes in rRNA modification patterns can affect protein synthesis in a manner that has serious consequences for bacterial pathogenicity.