2'-O-methylation of eukaryotic ribosomal RNA (r)RNA, essential for ribosome function, is catalysed by box C/D small nucleolar (sno)RNPs. The RNA components of these complexes (snoRNAs) contain one or two guide sequences, which, through base-pairing, select the rRNA modification site. Adjacent to the guide sequences are protein-binding sites (the C/D or C'/D' motifs). Analysis of >2000 yeast box C/D snoRNAs identified additional conserved sequences in many snoRNAs that are complementary to regions adjacent to the rRNA methylation site. This 'extra base-pairing' was also found in many human box C/D snoRNAs and can stimulate methylation by up to five-fold. Sequence analysis, combined with RNA-protein crosslinking in Saccharomyces cerevisiae, identified highly divergent box C'/D' motifs that are bound by snoRNP proteins. In vivo rRNA methylation assays showed these to be active. Our data suggest roles for non-catalytic subunits (Nop56 and Nop58) in rRNA binding and support an asymmetric model for box C/D snoRNP organization. The study provides novel insights into the extent of the snoRNA-rRNA interactions required for efficient methylation and the structural organization of the snoRNPs.