Most previously reported RNA-cleaving DNAzymes require only a single divalent metal ion for catalysis. We recently reported a general trivalent lanthanide-dependent DNAzyme named Ce13d. This work shows that Ce13d requires both Na(+) and a trivalent lanthanide (e.g. Ce(3+)), simultaneously. This discovery is facilitated by the sequence similarity between Ce13d and a recently reported Na(+)-specific DNAzyme, NaA43. The Ce13d cleavage rate linearly depends on the concentration of both metal ions. Sensitized Tb(3+) luminescence and DMS footprinting experiments indicate that the guanines in the enzyme loop are important for Na(+)-binding. The Na(+) dissociation constants of Ce13d measured from the cleavage activity assay, Tb(3+) luminescence and DMS footprinting are 24.6, 16.3 and 47 mM, respectively. Mutation studies indicate that the role of Ce(3+) might be replaced by G23 in NaA43. Ce(3+) functions by stabilizing the transition state phosphorane, thus promoting cleavage. G23 competes favorably with low concentration Ce(3+) (below 1 μM). The G23-to-hypoxanthine mutation suggests the N1 position of the guanine as a hydrogen bond donor. Together, Ce13d has two distinct metal binding sites, each fulfilling a different role. DNAzymes can be quite sophisticated in utilizing metal ions for catalysis and molecular recognition, similar to protein metalloenzymes.