DNA nanomotors are synthetic biochemical devices whose motion can be controlled at the molecular scale. Some DNA devices require several exogenous additions of different types of fuel to operate, which limits their potential uses. However, several devices that operate autonomously have recently been described. One such DNA nanomotor, based on a 10-23 DNA enzyme (DNAzyme), was introduced by Chen, Wang, and Mao (Angew. Chem., Int. Ed. 2004, 43, 3554). Although this DNAzyme nanomotor operates autonomously, its performance degrades over time in experiments. In this paper, we describe a mathematical model that predicts this degradation by accounting for the gradual accumulation of waste in the system. We also introduce and experimentally demonstrate two improved versions of the DNAzyme nanomotor. In particular, the new nanomotor systems use the enzyme ribonuclease H to selectively digest waste, resulting in nanomotors whose performance does not degrade significantly over time.