Type II restriction endonucleases (ENases) cleave DNA with remarkable sequence specificity. Their discovery in 1970 and studies on molecular genetics and biochemistry carried out over the past four decades laid foundations for recombinant DNA techniques. Today, restriction enzymes are indispensable tools in molecular biology and molecular medicine and a paradigm for proteins that specifically interact with DNA as well as a challenging target for protein engineering. The sequence-structure-function relationships for these proteins are therefore of central interest in biotechnology. However, among numerous ENase sequences, only a few exhibit statistically significant similarity in pairwise comparisons, which was initially interpreted as evidence for the lack of common origin. Nevertheless, X-ray crystallographic studies of seemingly dissimilar type II ENases demonstrated that they share a common structural core and metal-binding / catalytic site, arguing for extreme divergence rather than independent evolution. A similar nuclease domain has been also identified in various enzymes implicated in DNA repair and recombination. Ironically, following the series of crystallographic studies suggesting homology of all type II ENases, bioinformatic studies provided evidence that some restriction enzymes are in fact diverged members of unrelated nuclease superfamilies: Nuc, HNH and GIY-YIG. Hence, the restriction enzymes as a whole, represent a group of functionally similar proteins, which evolved on multiple occasions and subsequently diverged into the “midnight zone” of homology, where common origins within particular groups can be inferred only from structure-guided comparisons. The structure-guided approaches used for this purpose include: identification of functionally important residues using superposition of atomic coordinates, alignment of sequence profiles enhanced by secondary structures, fold recognition, and homology modeling. This review covers recent results of comparative analyses of restriction enzymes from the four currently known superfamilies of nucleases with distinct folds, using crystallographic and bioinformatic methods, with the emphasis on theoretical predictions and their experimental validation by site-directed mutagenesis and biochemical analyses of the mutants.