The C5-methylation of uracil to form 5-methyluracil (m5U) is a ubiquitous base modification of nucleic acids. Four enzyme families have converged to catalyze this methylation using different chemical solutions. Here, we investigate the evolution of 5-methyluracil synthase families in Mollicutes, a class of bacteria that has undergone extensive genome erosion. Many mollicutes have lost some of the m5U methyltransferases present in their common ancestor. Cases of duplication and subsequent shift of function are also described. For example, most members of the Spiroplasma subgroup use the ancestral tetrahydrofolate-dependent TrmFO enzyme to catalyze the formation of m5U54 in tRNA, while a TrmFO paralog (termed RlmFO) is responsible for m5U1939 formation in 23S rRNA. RlmFO has replaced the S-adenosyl-L-methionine (SAM)-enzyme RlmD that adds the same modification in the ancestor and which is still present in mollicutes from the Hominis subgroup. Another paralog of this family, the TrmFO-like protein, has a yet unidentified function that differs from the TrmFO and RlmFO homologs. Despite having evolved towards minimal genomes, the mollicutes possess a repertoire of m5U-modifying enzymes that is highly dynamic and has undergone horizontal transfer.