Single-stranded DNA molecules have the capacity to adopt catalytically active structures known as DNAzymes, although the fundamental limits of this ability have not been determined. Starting with a parent DNAzyme composed of all four types of standard nucleotides, we conducted a search of the surrounding sequence space to identify functional derivatives with catalytic cores composed of only three, and subsequently only two types of nucleotides. We provide the first report of a DNAzyme that contains only guanosine and cytidine deoxyribonucleotides in its catalytic domain, which consists of just 13 nucleotides. This DNAzyme catalyzes the Mn(2+)-dependent cleavage of an RNA phosphodiester bond approximately 5300-fold faster than the corresponding uncatalyzed reaction, but approximately 10,000-fold slower than the parent. The demonstration of a catalytic DNA molecule made from a binary nucleotide alphabet broadens our understanding of the fundamental limits of nucleic-acid-mediated catalysis.