RNA-cleaving deoxyribozymes have found broad application as useful tools for RNA biochemistry. However, tedious in vitro selection procedures combined with laborious characterization of individual candidate catalysts hinder the discovery of novel catalytic motifs. Here, we present a new high-throughput sequencing method, DZ-seq, which directly measures activity and localizes cleavage sites of thousands of deoxyribozymes. DZ-seq exploits A-tailing followed by reverse transcription with an oligo-dT primer to capture the cleavage status and sequences of both deoxyribozyme and RNA substrate. We validated DZ-seq by conventional analytical methods and demonstrated its utility by discovery of novel deoxyribozymes that allow for cleaving challenging RNA targets or the analysis of RNA modification states.