The peninsula of Baja California has a complex geological history that has strongly affected the regional biota. Genealogical histories of many species have revealed congruent patterns, which suggest that the peninsula was temporarily submerged at two locations. We sequenced a total of 1953 base pairs (bp) of the mitochondrial genome for 42 specimens of the zebra-tailed lizard (Callisaurus draconoides). The resulting maternal genealogy supports the former existence of a mid-peninsular seaway and a Plio-Quaternary seaway across the Isthmus of La Paz. In addition, a genealogical break is revealed in the vicinity of Loreto. This genealogical break may have resulted from prolonged submergence of the Loreto Basin during Pliocene. The mid-peninsular seaway may have occurred as early as late Miocene, at a time significantly earlier than previously hypothesized. Comparison with other genealogies and geological evidence suggests that current models on the evolution of Baja California's fauna are temporally shallow. The deep genealogical patterns of C. draconoides also disagree with the very limited population differentiation previously reported for allozyme markers, suggesting that maternal history may not be an appropriate approximation for population differentiation.