Recent investigations on the evolutionary history of the common midwife toad (Alytes obstetricans) revealed high levels of geographically structured genetic diversity but also a situation where delineation of major historical lineages and resolution of their relationships are much more complex than previously thought. We studied sequence variation in one mitochondrial and four nuclear genes throughout the entire distribution range of all recognized A. obstetricans subspecies to infer the evolutionary processes that shaped current patterns of genetic diversity and population subdivision. We found six divergent, geographically structured mtDNA haplogroups diagnosing population lineages, and varying levels of admixture in nuclear markers. Given the timeframe inferred for the splits between major lineages, the climatic and environmental changes that occurred during the Pleistocene seem to have shaped the diversification history of A. obstetricans. Survival of populations in allopatric refugia through the Ice Ages supports the generality of the "refugia-within-refugia" scenario for the Iberian Peninsula. However, lineages corresponding to subspecies A. o. almogavarii, A. o. pertinax, A. o. obstetricans, and A. o. boscai responded differently to Pleistocene climatic oscillations after diverging from a common ancestor. Alytes o. obstetricans expanded northward from a northern Iberian refugium through the western Pyrenees, leaving a signal of contrasting patterns of genetic diversity, with a single mtDNA haplotype north of the Pyrenees from SW France to Germany. Both A. o. pertinax and A. o. boscai are widespread and genetically diverse in Iberia, the latter comprising two divergent lineages with a long independent history. Finally, A. o. almogavarii is mostly restricted to the north-eastern corner of Iberia north of the Ebro river, with additional populations in a small region in south-eastern France. This taxon exhibits unparalleled levels of genetic diversity and little haplotype sharing with other lineages, suggesting a process of incipient speciation.