Two previously undetected domains were identified in a variety of RNA-binding proteins, particularly RNA-modifying enzymes, using methods for sequence profile analysis. A small domain consisting of 60-65 amino acid residues was detected in the ribosomal protein S4, two families of pseudouridine synthases, a novel family of predicted RNA methylases, a yeast protein containing a pseudouridine synthetase and a deaminase domain, bacterial tyrosyl-tRNA synthetases, and a number of uncharacterized, small proteins that may be involved in translation regulation. Another novel domain, designated PUA domain, after PseudoUridine synthase and Archaeosine transglycosylase, was detected in archaeal and eukaryotic pseudouridine synthases, archaeal archaeosine synthases, a family of predicted ATPases that may be involved in RNA modification, a family of predicted archaeal and bacterial rRNA methylases. Additionally, the PUA domain was detected in a family of eukaryotic proteins that also contain a domain homologous to the translation initiation factor eIF1/SUI1; these proteins may comprise a novel type of translation factors. Unexpectedly, the PUA domain was detected also in bacterial and yeast glutamate kinases; this is compatible with the demonstrated role of these enzymes in the regulation of the expression of other genes. We propose that the S4 domain and the PUA domain bind RNA molecules with complex folded structures, adding to the growing collection of nucleic acid-binding domains associated with DNA and RNA modification enzymes. The evolution of the translation machinery components containing the S4, PUA, and SUI1 domains must have included several events of lateral gene transfer and gene loss as well as lineage-specific domain fusions.