Ribosomal RNA (rRNA) carries extensive 2′′-O-methyl marks at functionally important sites. This simple chemical modification is thought to confer stability, promote RNA folding, and contribute to generate a heterogenous ribosome population with a yet-uncharacterized function. 2′′-O-methylation occurs both in archaea and eukaryotes and is accomplished by the Box C/D RNP enzyme in an RNA-guided manner. Extensive and partially conflicting structural information exists for the archaeal enzyme, while no structural data is available for the eukaryotic enzyme. The yeast Box C/D RNP consists of a guide RNA, the RNA-primary binding protein Snu13, the two scaffold proteins Nop56 and Nop58, and the enzymatic module Nop1. Here we present the high-resolution structure of the eukaryotic Box C/D methyltransferase Nop1 from Saccharomyces cerevisiae bound to the amino-terminal domain of Nop56. We discuss similarities and differences between the interaction modes of the two proteins in archaea and eukaryotes and demonstrate that eukaryotic Nop56 recruits the methyltransferase to the Box C/D RNP through a protein-protein interface that differs substantially from the archaeal orthologs. This study represents a first achievement in understanding the evolution of the structure and function of these proteins from archaea to eukaryotes.