Identification of species in natural populations has recently received increased attention with a number of investigators proposing rigorous methods for species delimitation. Morphologically conservative species (or species complexes) with deep phylogenetic histories (and limited gene flow) are likely to pose particular problems when attempting to delimit species, yet this is crucial to comparative studies of the geography of speciation. We apply two methods of species delimitation to an ancient group of lizards (genus Xantusia) that occur throughout southwestern North America. Mitochondrial cytochrome b and nicotinamide adenine dinucleotide dehydrogenase subunit 4 gene sequences were generated from samples taken throughout the geographic range of Xantusia. Maximum likelihood, Bayesian, and nested cladogram analyses were used to estimate relationships among haplotypes and to infer evolutionary processes. We found multiple well-supported independent lineages within Xantusia, for which there is considerable discordance with the currently recognized taxonomy. High levels of sequence divergence (21.3%) suggest that the pattern in Xantusia may predate the vicariant events usually hypothesized for the fauna of the Baja California peninsula, and the existence of deeply divergent clades (18.8%-26.9%) elsewhere in the complex indicates the occurrence of ancient sundering events whose genetic signatures were not erased by the late Wisconsin vegetation changes. We present a revised taxonomic arrangement for this genus consistent with the distinct mtDNA lineages and discuss the phylogeographic history of this genus as a model system for studies of speciation in North American deserts.