During the Pleistocene, the habitat of the noctule bat (Nyctalus noctula) was limited to small refuge areas located in Southern Europe, whereas the species is now widespread across this continent. Using mtDNA (control region and ND1 gene) polymorphisms, we asked whether this recolonization occurred through bottlenecks and whether it was accompanied by population growth. Sequences of the second hypervariable domain of the control region were obtained from 364 noctule bats representing 18 colonies sampled across Europe. This yielded 108 haplotypes that were depicted on a minimum spanning tree that showed a starlike structure with two long branches. Additional sequences obtained from the ND1 gene confirmed that the different parts of the MST correspond to three clades which diverged before the Last Glacial Maximum (18,000 yrC¹⁴ BP), leading to the conclusion that the noctule bat survived in several isolated refugia. Partitioning populations into coherent geographical groups divided our samples (φCT = 0.17; P = 0.01) into a group of highly variable nursing colonies from central and eastern Europe and less variable, isolated colonies from western and southern Europe. Demographic analyses suggest that populations of the former group underwent demographic expansions either after the Younger Dryas (11,000–10,000 yrC¹⁴ BP), assuming a fast mutation rate for HV II, or during the Pleistocene, assuming a conventional mutation rate. We discuss the fact that the high genetic variability (h = 0.69–0.96; π = 0.006–0.013) observed in nursing colonies that are located some distance from potential Pleistocene refugia is probably due to the combined effect of rapid evolution of the control region in growing populations and a range shift of noctule populations parallel to the recovery of forests in Europe after the last glaciations.