Deoxyribozymes (DNA catalysts) have been reported for cleavage of RNA phosphodiester linkages, but cleaving peptide or DNA phosphodiester linkages is much more challenging. Using in vitro selection, here we identified deoxyribozymes that sequence specifically hydrolyze DNA with multiple turnover and with a rate enhancement of 108 (possibly as high as 1014). The new DNA catalysts require both Mn2+ and Zn2+, which is noteworthy because many natural DNA nucleases are bimetallic protein enzymes.