In Europe, southern peninsulas served as refugia during cold periods in the Pleistocene, acting both as centres of origin of endemisms and as sources from which formerly glaciated areas were recolonized during interglacial periods. Previous studies have revealed that within the main refugial areas, intraspecific lineages often survived in allopatric refugia. We analysed two mitochondrial markers (nad4, control region, approximately 1.4 kb) in 103 individuals representing the entire distribution of Lissotriton boscai, a newt endemic to the western Iberian Peninsula. We inferred the evolutionary history of the species through phylogenetic, phylogeographic and historical demographic analyses. The results revealed unexpected, deep levels of geographically structured genetic variability. We identified two main evolutionary lineages, each containing three well-supported clades. The first historical split involved populations from central-southwestern coastal Portugal and the ancestor of all the remaining populations around 5.8 million years ago. Both lineages were subsequently fragmented into different population groups between 2.5 and 1.2 million years ago. According to nested clade analysis, at lower hierarchical levels the patterns suggest restricted gene flow with isolation by distance, whereas at higher levels the clades exhibit signatures of contiguous range expansion. Bayesian Skyline Plots show recent bottlenecks, followed by demographic expansions in all lineages. The significant genetic structure found is consistent with long-term survival of populations in allopatric refugia, supporting the 'refugia-within-refugia' scenario for southern European peninsulas. The comparison of our results with other co-distributed species highlights the generality of this hypothesis for the Iberian herpetofauna and suggests that Mediterranean refuges had more relevance for the composition and distribution of present biodiversity patterns than currently acknowledged. We briefly discuss the taxonomic and conservation implications of our results.