The origin of Saharan biodiversity is poorly understood, in part because the geological and paleoclimatic events that presumably shaped species diversity are still controversial, but also because few studies have explored causal explanations for the origin of Saharan diversity using a phylogenetic framework. Here, we use mtDNA (16S and ND4 genes) and nDNA (MC1R and CMOS genes) to infer the relationships and biogeographic history of North African agamas (genus Agama). Agamas are conspicuous, diverse and abundant African lizards that also occur in the Saharan xeric and mesic environments. Our results revealed the presence of three Agama lineages in North Africa: one Afrotropical, one Sahelo-Saharan, and one broadly distributed in North Africa and mainly Saharan. Southern Mauritania contains the highest known diversity, with all three lineages present. Results suggest that agamas colonized the Sahara twice, but only one lineage was able to radiate and diversify there. Species in the Saharan lineage are mostly allopatric, and their splitting, genetic diversity and distribution are greatly explained by mountain ranges. One species in this lineage has colonized the Mediterranean climatic zone (A. impalearis), and another one the Sahel savannah (A. boueti). The other lineage to colonize the Sahara corresponds to A. boulengeri, an eminently Sahelian species that also inhabits Saharan mountain ranges in Mauritania and Mali. Phylogenetic analyses indicate that allopatric montane populations within some currently recognized species are also genetically divergent. Our study therefore concludes that vicariant speciation is a leading motor of species diversification in the area: Inside the Sahara, associated to mountain-ranges isolated by dune seas and bare plains; outside, associated to less harsh climates to the North and South. Paleoclimatic oscillations are suggested as causal explanations of the vicariant distribution and origin of species. Agamas are thought to have colonized northern Africa during wet periods, with subsequent dry periods fragmenting species distribution and leading to allopatric populations associated to milder and wetter climates in the Mediterranean, Sahel, and in Saharan mountains, in an island-model fashion. Finally, our results support the synonymization of A. castroviejoi with A. boueti, the reciprocal monophyly of all other North African agamas, and suggest one candidate species within A. boulengeri.