In contrast to mRNAs, which are templates for translating proteins, non-protein coding (npc) RNAs (also known as 'non-coding' RNA, ncRNA), exhibit various functions in different compartments and developmental stages of the cell. Small nucleolar RNAs (snoRNAs), one of the largest classes of npcRNAs, guide post-transcriptional modifications of other RNAs that are crucial for appropriate RNA folding as well as for RNA-RNA and RNA-protein interactions. Although snoRNA genes comprise a significant fraction of the eutherian genome, identifying and characterizing large numbers of them is not sufficiently accessible by classical computer searches alone. Furthermore, most previous investigations of snoRNAs yielded only limited indications of their evolution. Using data obtained by a combination of high-throughput cDNA library screening and computational search strategies based on a modified DNAMAN program, we characterized 151 npcRNAs, and in particular 121 snoRNAs, from Caenorhabditis elegans and extensively compared them with those in the related, Caenorhabditis briggsae. Detailed comparisons of paralog snoRNAs in the two nematodes revealed, in addition to trans-duplication, a novel, cis-duplication distribution strategy with insertions near to the original loci. Some snoRNAs coevolved with their modification target sites, demonstrating the close interaction of complementary regions. Some target sites modified by snoRNAs were changed, added or lost, documenting a high degree of evolutionary plasticity of npcRNAs.