Natural ribozymes require metal ion cofactors that aid both in structural folding and in chemical catalysis. In contrast, many protein enzymes produce dramatic rate enhancements using only the chemical groups that are supplied by their constituent amino acids. This fact is widely viewed as the most important feature that makes protein a superior polymer for the construction of biological catalysts. Herein we report the in vitro selection of a catalytic DNA that uses histidine as an active component for an RNA cleavage reaction. An optimized deoxyribozyme from this selection requires L-histidine or a closely related analog to catalyze RNA phosphoester cleavage, producing a rate enhancement of approximately 1-million-fold over the rate of substrate cleavage in the absence of enzyme. Kinetic analysis indicates that a DNA-histidine complex may perform a reaction that is analogous to the first step of the proposed catalytic mechanism of RNase A, in which the imidazole group of histidine serves as a general base catalyst. Similarly, ribozymes of the "RNA world" may have used amino acids and other small organic cofactors to expand their otherwise limited catalytic potential.