In Escherichia coli, RlmB catalyzes the methylation of guanosine 2251, a modification conserved in the peptidyltransferase domain of 23S rRNA. The crystal structure of this 2′O-methyltransferase has been determined at 2.5 Å resolution. RlmB consists of an N-terminal domain connected by a flexible extended linker to a catalytic C-terminal domain and forms a dimer in solution. The C-terminal domain displays a divergent methyltransferase fold with a unique knotted region, and lacks the classic AdoMet binding site features. The N-terminal domain is similar to ribosomal proteins L7 and L30, suggesting a role in 23S rRNA recognition. The conserved residues in this novel family of 2′O-methyltransferases cluster in the knotted region, suggesting the location of the catalytic and AdoMet binding sites.