The understanding of the diversity of species in the Palearctic and the processes that have generated it is still weak for large parts of the arid areas of North Africa and Arabia. Reptiles are among their most remarkable representatives, with numerous groups well adapted to the diverse environments. The Ptyodactylus geckos are a strictly rock-dwelling genus with homogeneous morphology distributed across mountain formations and rocky plateaus from the western African ranges in Mauritania and the Maghreb to the eastern tip of the Arabian Peninsula, with an isolated species in southern Pakistan. Here, we use a broad sampling of 378 specimens, two mitochondrial (12S and cytb) and four nuclear (c-mos, MC1R, ACM4, RAG2) markers in order to obtain the first time-calibrated molecular phylogeny of the genus and place its diversification in a temporal framework. The results reveal high levels of intraspecific variability, indicative of undescribed diversity, and they do not support the monophyly of one species (P. ragazzii). Ptyodactylus species are allopatric across most of their range, which may relate to their high preference for the same type of structural habitat. The onset of their diversification is estimated to have occurred in the Late Oligocene, while that of several deep clades in the phylogeny took place during the Late Miocene, a period when an increase in aridification in North Africa and Arabia initiated.