Type-II restriction-modification (R-M) systems comprise two enzymes, a DNA methyltransferase (MTase) and a restriction endonuclease (ENase), each of which specifically interact with the same 4-8 bp sequence. All type-II MTases share several amino acid (aa) sequence motifs, which makes an evolutionary relatedness among these enzymes probable. The type-II ENases, in contrast, except for some homologous isoschizomers, do not share significant aa sequence similarity. Therefore, ENases in general have been considered unrelated. Here we show that in addition to the analysis of the genotype (aa sequence), a comparison of the phenotype (recognition sequence) of these enzymes can provide independent information regarding evolutionary relationships, and thereby, help to analyze the significance of weak aa sequence similarities. Multistep Monte-Carlo analyses were employed to demonstrate that the recognition sequences of those ENases, which were found to be related by a progressive multiple aa sequence alignment, are more similar to each other than would be expected by chance. This analysis supports the notion that not only type-II MTases, but also type-II ENases did not arise independently in evolution, but rather evolved from one or a few primordial DNA-modifying and DNA-cleaving enzymes, respectively.