Biointegrative information processing systems offer a great advantage to autonomous biodevices, as their capacity for biological computation provides the ability to sense the state of more complex environments and better integrate with downstream biological regulation systems. Deoxyribozymes (DNAzymes) and aptamers are of interest to such computational biosensing systems due to the enzymatic properties of DNAzymes and the ligand-inducible conformational structures of aptamers. Herein, we describe a novel method for providing ligand-responsive allosteric control to a DNAzyme using an RNA aptamer. We designed a NOT-logic-compliant E6 DNAzyme to be complementary to an RNA aptamer targeting theophylline, such that the aptamer competitively interacted with either theophylline or the DNAzyme, and disabled the DNAzyme only when theophylline concentration was below a given threshold. Out of our seven designed “complexing aptazymes,” three demonstrated effective theophylline-responsive allosteric regulation (2.84 ± 3.75%, 4.97 ± 2.92%, and 8.91 ± 4.19% activity in the absence of theophylline; 46.29 ± 3.36%, 50.70 ± 10.15%, and 61.26 ± 6.18% activity in the presence of theophylline). Moreover, the same three complexing aptazymes also demonstrated the ability to semi-quantitatively determine the concentration of theophylline present in solution, successfully discriminating between therapeutically ineffective (<20 μM), safe (20–100 μM), and toxic (>100 μM) theophylline concentrations. Our method of using an RNA aptamer for ligand-responsive allosteric control of a DNAzyme expands the way aptamers can be configured for biosensing, and suggests a pathway for embedding DNAzymes to provide enhanced information processing and control of biological systems.