Methylation of cytidines at carbon-5 is a common posttranscriptional RNA modification encountered across all domains of life. Here, we characterize the modifications of C1942 and C1962 in Thermus thermophilus 23 S rRNA as 5-methylcytidines (m(5)C) and identify the two associated methyltransferases. The methyltransferase modifying C1942, named RlmO, has not been characterized previously. RlmO modifies naked 23 S rRNA, but not the assembled 50 S subunit or 70 S ribosomes. The x-ray crystal structure of this enzyme in complex with the S-adenosyl-l-methionine cofactor at 1.7 Å resolution confirms that RlmO is structurally related to other m(5)C rRNA methyltransferases. Key residues in the active site are located similar to the further distant 5-methyluridine methyltransferase RlmD, suggestive of a similar enzymatic mechanism. RlmO homologues are primarily found in mesophilic bacteria related to T. thermophilus. In accordance, we find that growth of the T. thermophilus strain with an inactivated C1942 methyltransferase gene is not compromised at non-optimal temperatures.