Asexuality is rare in animals in spite of its apparent advantage relative to sexual reproduction, indicating that it must be associated with profound costs [1-9]. One expectation is that reproductive advantages gained by new asexual lineages will be quickly eroded over time [3, 5-7]. Ancient asexual taxa that have evolved and adapted without sex would be "scandalous" exceptions to this rule, but it is often difficult to exclude the possibility that putative asexuals deploy some form of "cryptic" sex, or have abandoned sex more recently than estimated from divergence times to sexual relatives [10]. Here we provide evidence, from high intraspecific divergence of mitochondrial sequence and nuclear allele divergence patterns, that several independently derived Timema stick-insect lineages have persisted without recombination for more than a million generations. Nuclear alleles in the asexual lineages displayed significantly higher intraindividual divergences than in related sexual species. In addition, within two asexuals, nuclear allele phylogenies suggested the presence of two clades, with sequences from the same individual appearing in both clades. These data strongly support ancient asexuality in Timema and validate the genus as an exceptional opportunity to attack the question of how asexual reproduction can be maintained over long periods of evolutionary time.