Background: Phylogeography is an important tool that can be used to reveal cryptic biodiversity and to better understand the processes that promote lineage diversification. We studied the phylogeographic history of the Arboreal Salamander (Aneides lugubris), a wide-ranging species endemic to the California floristic province. We used multi-locus data to reconstruct the evolutionary history of A. lugubris and to discover the geographic location of major genetic breaks within the species. We also used species distribution modeling and comparative phylogeography to better understand the environmental factors that have shaped the genetic history of A. lugubris. Results: We found six major mitochondrial clades in A. lugubris. Nuclear loci supported the existence of at least three genetically distinct groups, corresponding to populations north of the San Francisco Bay and in the Sierra Nevada, in the Santa Cruz Mountains, and in the central coast and southern California. All of the genetic breaks in mitochondrial and nuclear loci corresponded to regions where historical barriers to dispersal have been observed in other species. Geologic or water barriers likely were the most important factors restricting gene flow among clades. Climatic unsuitability during glacial maximum may have contributed to the isolation of the mitochondrial clades in the central coast and southern California. A projection of our species distribution model to a future scenario with a moderate amount of climate change suggests that most of the range of A. lugubris will remain climatically suitable, but climatic conditions in the Sierra Nevada and low elevation areas in Southern California are likely to deteriorate. Conclusions: Aneides lugubris contains substantial cryptic genetic diversity as a result of historical isolation of populations. At least two (and perhaps three) evolutionarily significant units in A. lugubris merit protection; all six mitochondrial clades should be considered as management units within the species.