We report that micromolar concentrations of lanthanide ions can be required cofactors for DNA-hydrolyzing deoxyribozymes. Previous work identified deoxyribozymes that simultaneously require both Zn2+ and Mn2+ to achieve DNA-catalyzed DNA hydrolysis (1012 rate enhancement); a mutant of one such DNA catalyst requires only Zn2+. Here we show that in vitro selection in the presence of 10 μM lanthanide ion (Ce3+, Eu3+, or Yb3+) along with 1 mM Zn2+ leads to numerous DNA-hydrolyzing deoxyribozymes that strictly require the lanthanide ion as well as Zn2+ for catalytic activity. These DNA catalysts have a range of lanthanide dependences, including some deoxyribozymes that strongly favor one particular lanthanide ion (e.g., Ce3+ ≫ Eu3+ ≫ Yb3+) and others that function well with more than one lanthanide ion. Intriguingly, two of the Yb3+-dependent deoxyribozymes function well with Yb3+ alone (Kd,app ∼ 10 μM, in the absence of Zn2+) and have little or no activity with Eu3+ or Ce3+. In contrast to these selection outcomes when lanthanide ions were present, new selections with Zn2+ or Mn2+ alone, or Zn2+ with Mg2+/Ca2+, led primarily to deoxyribozymes that cleave DNA by deglycosylation and β-elimination rather than by hydrolysis, including several instances of depyrimidination. We conclude that lanthanide ions warrant closer attention as cofactors when identifying new nucleic acid catalysts, especially for applications in which high concentrations of polyvalent metal ion cofactors are undesirable.