We hypothesize the phylogenetic relationships of the agamid genus Phrynocephalusto assess how past environmental changes shaped the evolutionary andbiogeographic history of these lizards and especially the impact of paleogeographyand climatic factors. Phrynocephalus is one of the most diverse and taxonomicallyconfusing lizard genera. As a key element of Palearctic deserts, it serves as apromising model for studies of historical biogeography and formation of aridhabitats in Eurasia. We used 51 samples representing 33 of 40 recognized species ofPhrynocephalus covering all major areas of the genus. Molecular data included fourmtDNA (COI, ND2, ND4, Cytb; 2,703 bp) and four nuDNA protein-coding genes(RAG1, BDNF, AKAP9, NKTR; 4,188 bp). AU-tests were implemented to test forsignificant differences between mtDNA- and nuDNA-based topologies. A time-calibrated phylogeny was estimated using a Bayesian relaxed molecular clock withnine fossil calibrations. We reconstructed the ancestral area of origin, biogeographicscenarios, body size, and the evolution of habitat preference. Phylogenetic analysesof nuDNA genes recovered a well-resolved and supported topology. Analysesdetected significant discordance with the less-supported mtDNA genealogy. Theposition of Phrynocephalus mystaceus conflicted greatly between the two datasets.MtDNA introgression due to ancient hybridization best explained this result.Monophyletic Phrynocephalus contained three main clades: (I) oviparous speciesfrom south-western and Middle Asia; (II) viviparous species of Qinghai–TibetanPlateau (QTP); and (III) oviparous species of the Caspian Basin, Middle and CentralAsia. Phrynocephalus originated in late Oligocene (26.9 Ma) and modern speciesdiversified during the middle Miocene (14.8–13.5 Ma). The reconstruction ofancestral areas indicated that Phrynocephalus originated in Middle East–southernMiddle Asia. Body size miniaturization likely occurred early in the history ofPhrynocephalus. The common ancestor of Phrynocephalus probably preferred sandysubstrates with the inclusion of clay or gravel. The time of Agaminae radiation andorigin of Phrynocephalus in the late Oligocene significantly precedes the landbridgebetween Afro-Arabia and Eurasia in the Early Miocene. Diversification ofPhrynocephalus coincides well with the mid-Miocene climatic transition when arapid cooling of climate drove progressing aridification and the Paratethys salinitycrisis. These factors likely triggered the spreading of desert habitats in CentralEurasia, which Phrynocephalus occupied. The origin of the viviparous Tibetan cladehas been associated traditionally with uplifting of the QTP; however, further studiesare needed to confirm this. Progressing late Miocene aridification, the decrease ofthe Paratethys Basin, orogenesis, and Plio–Pleistocene climate oscillations likelypromoted further diversification within Phrynocephalus. We discuss Phrynocephalustaxonomy in scope of the new analyses.