We report an investigation of the functional relationship between two independently selected RNA-cleaving DNAzymes, NaA43, and Ce13, through in vitro selection. The NaA43 DNAzyme was obtained through a combination of gel-based and column-based in vitro selection in the presence of Na(+) and reported to be highly selective for Na(+) over other metal ions. The Ce13 DNAzyme was isolated via a gel-based method in the presence of Ce(4+) and found to be active with trivalent lanthanides, Y(3+) and Pb(2+). Despite completely different activities reported for the two DNAzymes, they share a high level of sequence similarity (~60% sequence identity). In this work, we systematically analyzed the activity of both DNAzymes to elucidate their potential functional relationship. We found that Na(+) is an obligate cofactor of the Ce13 DNAzyme and lanthanides cannot initiate the cleavage reaction in the absence of Na(+). Hence, we conclude that the Ce13 DNAzyme is a variant of the NaA43 DNAzyme that catalyzes reaction in the presence Na(+) and also utilizes lanthanides in a potentially allosteric manner. These results have identified a new DNAzyme motif that is not only remarkably Na(+)-specific, but also allows for design of novel allosteric DNAzymes for different biotechnological applications.