The PD-(D/E)XK nuclease domains, initially identified in type II restriction enzymes, serve as models for studying aspects of protein-DNA interactions, mechanisms of phosphodiester hydrolysis, and provide indispensable tools for techniques in genetic engineering and molecular medicine. However, the low degree of amino acid conservation hampers the possibility of identification of PD-(D/E)XK superfamily members based solely on sequence comparisons. In several proteins implicated in DNA recombination and repair the restriction enzyme-like nuclease domain has been found only after the corresponding structures were determined experimentally. Here, we identified highly diverged variants of the PD-(D/E)XK domain in many proteins and open reading frames using iterative database searches and progressive, structure-guided alignment of sequence profiles. We predicted the possible cellular function for many hypothetical proteins based on their relative similarity to characterized nucleases or observed presence of additional domains. We also identified the nuclease domain in genuine recombinases and restriction enzymes, whose homology to other PD-(D/E)XK enzymes has not been demonstrated previously. The first superfamily-wide comparative analysis, not limited to nucleases of known structure, will guide cloning and characterization of novel enzymes and planning new experiments to better understand those already studied.