Pleistocene aridification in central North America caused many temperate forest-associated vertebrates to split into eastern and western lineages. Such divisions can be cryptic when Holocene expansions have closed the gaps between once-disjunct ranges or when local morphological variation obscures deeper regional divergences. We investigated such cryptic divergence in the gray fox (Urocyon cinereoargenteus), the most basal extant canid in the world. We also investigated the phylogeography of this species and its diminutive relative, the island fox (U. littoralis), in California. The California Floristic Province was a significant source of Pleistocene diversification for a wide range of taxa and, we hypothesized, for the gray fox as well. Alternatively, gray foxes in California potentially reflected a recent Holocene expansion from further south. We sequenced mitochondrial DNA from 169 gray foxes from the southeastern and southwestern United States and 11 island foxes from three of the Channel Islands. We estimated a 1.3% sequence divergence in the cytochrome b gene between eastern and western foxes and used coalescent simulations to date the divergence to approximately 500,000 years before present (YBP), which is comparable to that between recognized sister species within the Canidae. Gray fox samples collected from throughout California exhibited high haplotype diversity, phylogeographic structure, and genetic signatures of a late-Holocene population decline. Bayesian skyline analysis also indicated an earlier population increase dating to the early Wisconsin glaciation (~70,000 YBP) and a root height extending back to the previous interglacial (~100,000 YBP). Together these findings support California's role as a long-term Pleistocene refugium for western Urocyon. Lastly, based both on our results and re-interpretation of those of another study, we conclude that island foxes of the Channel Islands trace their origins to at least 3 distinct female founders from the mainland rather than to a single matriline, as previously suggested.