Antisense oligonucleotides and ribozymes have been used widely to regulate gene expression by targeting mRNAs in a sequence-specific manner. Long RNAs, however, are highly structured molecules. Thus, up to 90% of putative cleavage sites have been shown to be inaccessible to classical RNA based ribozymes or DNAzymes. Here, we report the use of modified nucleotides to overcome barriers raised by internal structures of the target RNA. In our attempt to cleave a broad range of picornavirus RNAs, we generated a DNAzyme against a highly conserved sequence in the 5\' untranslated region (5\' UTR). While this DNAzyme was highly efficient against the 5\' UTR of the human rhinovirus 14, it failed to cleave the identical target sequence within the RNA of the related coxsackievirus A21 (CAV-21). After introduction of 2\'-O-methyl RNA or locked nucleic acid (LNA) monomers into the substrate recognition arms, the DNAzyme degraded the previously inaccessible virus RNA at a high catalytic rate even to completion, indicating that nucleotides with high target affinity were able to compete successfully with internal structures. We then adopted this strategy to two DNAzymes that we had found to be inactive in our earlier experiments. The modified DNAzymes proved to be highly effective against their respective target structures. Our approach may be useful for other ribozyme strategies struggling with accessibility problems, especially when being restricted to unique target sites.