Using sensitive sequence profile searches and contextual information gleaned from domain architectures and predicted operons we identify a novel family of protein domains with predicted ribonuclease activity. These domains are found in the eukaryotic proteins typified by the Nedd4-binding protein 1 and the bacterial YacP-like proteins (Nedd4-BP1, YacP nucleases; NYN domains). We show that the NYN domain shares a common protein fold with two other previously characterized groups of nucleases, namely the PIN (PilT N-terminal) and FLAP/5' --> 3' exonuclease superfamilies. We also show that all these proteins share a common set of 4 acidic conserved residues that are predicted to constitute their active site. Based on the conservation of the acidic residues and structural elements we suggest that PIN and NYN domains are likely to bind only a single metal ion, unlike the FLAP/5' --> 3' exonuclease superfamily, which binds two metal ions. We also present evidence that the other conserved residues shared by all these three domains are likely to play critical roles in sensing the substrate and positioning the catalytic residues in the right conformation. Based on conserved gene neighborhoods we infer that the bacterial members are likely to be components of the processome/degradsome that process tRNAs or ribosomal RNAs. Eukaryotic versions appear to have undergone extensive functional diversification as suggested by the several distinctive multi-domain architectures showing fusions with various other RNA-binding domains like CCCH, PPR and KH domains. Interestingly, the eukaryotic NYN domains also show multiple fusions to the UBA domain, an ubiquitin-binding adaptor domain. This observation, together with the monoubiquitination of Nedd4-BP1 by the ubiquitin ligase Nedd4 suggests that the NYN domain proteins of eukaryotes are regulated by monoubiquitination. Given the localization of Nedd4-BP1 to punctuate nuclear bodies, it is likely that they are parts of nuclear RNA-processing complexes that are dependent on monoubiquitination for their assembly.