Abstract The Mediterranean Basin has experienced extensive change in geology and climate over the past six million years. Yet, the relative importance of key geological events for the distribution and genetic structure of the Mediterranean fauna remains poorly understood. Here, we use population genomic and phylogenomic analyses to establish the evolutionary history and genetic structure of common wall lizards (Podarcis muralis). This species is particularly informative because, in contrast to other Mediterranean lizards, it is widespread across the Iberian, Italian, and Balkan Peninsulas, and in extra-Mediterranean regions. We found strong support for six major lineages within P. muralis, which were largely discordant with the phylogenetic relationship of mitochondrial DNA. The most recent common ancestor of extant P. muralis was likely distributed in the Italian Peninsula, and experienced an “Out-of-Italy” expansion following the Messinian salinity crisis (∼5 Mya), resulting in the differentiation into the extant lineages on the Iberian, Italian, and Balkan Peninsulas. Introgression analysis revealed that both inter- and intraspecific gene flows have been pervasive throughout the evolutionary history of P. muralis. For example, the Southern Italy lineage has a hybrid origin, formed through admixture between the Central Italy lineage and an ancient lineage that was the sister to all other P. muralis. More recent genetic differentiation is associated with the onset of the Quaternary glaciations, which influenced population dynamics and genetic diversity of contemporary lineages. These results demonstrate the pervasive role of Mediterranean geology and climate for the evolutionary history and population genetic structure of extant species.