The 2'-O-methylation of the nucleoside at position 32 of tRNA is found in organisms belonging to the three domains of life. Unrelated enzymes catalyzing this modification in Bacteria (TrmJ) and Eukarya (Trm7) have already been identified, but until now, no information is available for the archaeal enzyme. In this work we have identified the methyltransferase of the archaeon Sulfolobus acidocaldarius responsible for the 2'-O-methylation at position 32. This enzyme is a homolog of the bacterial TrmJ. Remarkably, both enzymes have different specificities for the nature of the nucleoside at position 32. While the four canonical nucleosides are substrates of the Escherichia coli enzyme, the archaeal TrmJ can only methylate the ribose of a cytidine. Moreover, the two enzymes recognize their tRNA substrates in a different way. We have solved the crystal structure of the catalytic domain of both enzymes to gain better understanding of these differences at a molecular level.