The crystal structure of E. coli Fmu, determined at 1.65 A resolution for the apoenzyme and 2.1 A resolution in complex with AdoMet, is the first representative of the 5-methylcytosine RNA methyltransferase family that includes the human nucleolar proliferation-associated protein p120. Fmu contains three subdomains which share structural homology to DNA m(5)C methyltransferases and two RNA binding protein families. In the binary complex, the AdoMet cofactor is positioned within the active site near a novel arrangement of two conserved cysteines that function in cytosine methylation. The site is surrounded by a positively charged cleft large enough to bind its unique target stem loop within 16S rRNA. Docking of this stem loop RNA into the structure followed by molecular mechanics shows that the Fmu structure is consistent with binding to the folded RNA substrate.