Eukaryotic ribosomal RNA (rRNA) contains dozens of post-transcriptionally modified nucleotides. The most numerous type of modification, 2'-O-ribose methylation, requires a family of small nucleolar RNA genes (snoRNAs) which specify the position of methylation by direct base pairing interactions. SnoRNAs have not been reported in Bacteria or Archaea. Using biochemical and computational methods, we have identified archaeal snoRNA genes in species covering both major branches of the Archaea. Eighteen small sno-like RNAs (sRNAs) were cloned from the archaeon Sulfolobus acidocaldarius by co-immunoprecipitation with aFIB and aNOP56, the archaeal homologs of eukaryotic snoRNA-associated proteins. From the properties of these sRNAs, we trained a probabilistic model to search for archaeal sRNAs in archaeal genomic sequences. Over 200 additional sRNAs were found across five divergent archaeal genera from seven genomes. Many of these are confirmed experimentally or supported by comparative sequence analysis.