Although structures of many DNA-binding proteins have been solved, they fall into a limited number of folds. Here, we describe an approach that led to the finding of a novel DNA-binding fold. Based on the behavior of Type II restriction-modification gene complexes as mobile elements, our earlier work identified a restriction enzyme, R.Pabl, and its cognate modification enzyme in Pyrococcus abyssi through comparison of closely related genomes. While the modification methyltransferase was easily recognized, R.Pabl was predicted to have a novel 3D structure. We expressed cytotoxic R.Pabl in a wheat-germ-based cell-free translation system and determined its crystal structure. R.Pabl turned out to adopt a novel protein fold. Homodimeric R.Pabl has a curved anti-parallel beta-sheet that forms a 'half pipe'. Mutational and in silico DNA-binding analyses have assigned it as the double-strand DNA-binding site. Unlike most restriction enzymes analyzed, R.Pabl is able to cleave DNA in the absence of Mg2+. These results demonstrate the value of genome comparison and the wheat-germ-based system in finding a novel DNA-binding motif in mobile DNases and, in general, a novel protein fold in horizontally transferred genes.