We studied the phylogeography and population history of the white wagtail Motacilla alba, which has a vast breeding range, covering areas with different Pleistocene climatic histories. The mitochondrial NADH dehydrogenase subunit II gene (ND2) and Control Region (CR) were analyzed for 273 individuals from 45 localities. Our data comprised all nine subspecies of white wagtail. Four primary clades were inferred (M, N, SW and SE), with indications of M. grandis being nested within M. alba. The oldest split was between two haplotypes from the endemic Moroccan M. a. subpersonata (clade M) and the others, at 0.63-0.96 Mya; other divergences were at 0.31-0.38 Mya. The entire differentiation falls within the part of the Pleistocene characterized by Milankovitch cycles of large amplitudes and durations. Clade N was distributed across the northern Palearctic; clade SW in southwestern Asia plus the British Isles and was predicted by Ecological niche models (ENMs) to occur also in central and south Europe; and clade SE was distributed in central and east Asia. The deep divergence within M. a. subpersonata may reflect retention of ancestral haplotypes. Regional differences in historical climates have had different impacts on different populations: clade N expanded after the last glacial maximum (LGM), whereas milder Pleistocene climate of east Asia allowed clade SE a longer expansion time (since MIS 5); clade SW expanded over a similarly long time as clade SE, which is untypical for European species. ENMs supported these conclusions in that the northern part of the Eurasian continent was unsuitable during the LGM, whereas southern parts remained suitable. The recent divergences and poor structure in the mitochondrial tree contrasts strongly with the pronounced, well defined phenotypical differentiation, indicating extremely fast plumage divergence.