Allosteric control of deoxyribozymes is useful for a broad range of practical applications, such as nucleic acid sensing and DNA-computing. We found that the catalytic activity of a DNA-hydrolyzing deoxyribozyme could be allosterically regulated by adding short oligonucleotides. We used this technique to construct deoxyribozyme-based logic gates.