The complex geological and ecological processes that have generated high levels of biodiversity and endemism in the Baja California Peninsula have been the subject of intensive study. However, relatively little is known about phylogeography of the iconic endemic palm species of this region. We therefore analyzed a total of 2,294 bp of chloroplast and 738 bp of nuclear sequence data in 169 samples of five native palm species from Baja California, Sonora and Guadalupe Island. We found that Washingtonia and Brahea palms had low levels of genetic diversity and were highly structured, with the majority of species and major geographic regions being characterized by distinct haplotypes. We also found strong support for currently recognized species in Washingtonia, but our results were less clear cut for Brahea due to haplotype sharing. Furthermore, patterns of population structure were broadly consistent with historical vicariant events such as the inundation of the Isthmus of La Paz, the formation of the Sea of Cortez, and the more recent colonization and isolation of Guadalupe Island's palms. Our findings contribute toward a growing appreciation of the complexity of plant responses to past geological changes and also provide valuable baseline genetic data on relict American palm species.