The existence of clonally reproducing vertebrates has often served as a foil in attempts to explain the near-ubiquity of sexual reproduction in eukaryotes, but the absence of recombination, with its attendant limitation of new genotypes to those produced through mutations, restricts the adaptive ability of clonal organisms. It has been argued, therefore, that clonal vertebrate taxa have short lifespans. Variation in mitochondrial DNA (mtDNA) within clonal populations is interpreted instead as reflecting multiple, although limited, independent hybridization events. On the basis of an analysis of an average of 373 nucleotide pairs, we report here that the mtDNA of clonal, hybrid, gynogenetic mole salamanders (Ambystoma, Ambystomatidae) differs by 5% or more from mtDNA of their closest possible sexual relatives (A. jeffersonianum, A. laterale and A. texanum). Assuming usual rates of mtDNA divergence, these lineages have persisted for about 5 million years, far longer than estimated for other clonal vertebrate populations. The low mtDNA variability in the clonal lineages suggests that they have undergone population reductions during the Pleistocene.