Our understanding of the effect of Pleistocene climatic changes on the biodiversity of European mammals mostly comes from phylogeographic studies of non-subterranean mammals, while the influence of the glaciation cycles on subterranean mammals has received little attention. The lack of these data raises the question of how and to which extent the current amount and distribution of genetic variation in the subterranean mammals is the result of Pleistocene range contractions/expansions. The common mole (Talpa europaea) is a strictly subterranean mammal widespread across Europe and it represents one of the best candidate to study the influence of Quaternary climatic oscillation on subterranean mammals. Cytochrome b sequences, obtained from a sampling covering the majority of the distribution area, were used to evaluate if Pleistocene climate change influenced the evolution of T. europaea and left a trace in the genetic diversity comparable to that observed in non-subterranean small mammals. Subsequently we investigated the occurrence of glacial refugia by comparing the results of phylogeographic analysis with species distribution modelling. We found three differentiated mtDNA lineages, two restricted to Spain and Italy and a third one widespread across Europe. Phylogenetic inferences and molecular clock suggest that the Spanish moles represent a highly divergent and ancient lineage, highlighting for the first time the paraphyly of Talpa europaea. Furthermore, our analyses suggest that the genetic break between the Italian and the European lineages predates the last glacial phase. Historical demography and spatial principal component analysis further suggest that the last glacial maximum left a signature both in the Italian and in the European lineages. Genetic data combined with species distribution models support the presence of at least three putative glacial refugia in southern Europe (France, Balkan peninsula and Black sea) during the last glacial maximum that likely contributed to post-glacial recolonization of Europe. By contrast, the 58I talian lineage remained trapped in the Italian peninsula and, according to the pattern observed in other subterranean mammal, did not contribute to the recolonization of northern latitudes.