The level of genetic differentiation within and between evolutionary lineages of the common vole (Microtus arvalis) in Europe was examined by analyzing mitochondrial sequences from the control region (mtDNA) and 12 nuclear microsatellite loci (nucDNA) for 338 voles from 18 populations. The distribution of evolutionary lineages and the affinity of populations to lineages were determined with additional sequence data from the mitochondrial cytochrome b gene. Our analyses demonstrated very high levels of differentiation between populations (overall FST: mtDNA 70%; nucDNA 17%). The affinity of populations to evolutionary lineages was strongly reflected in mtDNA but not in nucDNA variation. Patterns of genetic structure for both markers visualized in synthetic genetic maps suggest a postglacial range expansion of the species into the Alps, as well as a potentially more ancient colonization from the northeast to the southwest of Europe. This expansion is supported by estimates for the divergence times between evolutionary lineages and within the western European lineage, which predate the last glacial maximum (LGM). Furthermore, all measures of genetic diversity within populations increased significantly with longitude and showed a trend toward increase with latitude. We conclude that the detected patterns are difficult to explain only by range expansions from separate LGM refugia close to the Mediterranean. This suggests that some M. arvalis populations persisted during the LGM in suitable habitat further north and that the gradients in genetic diversity may represent traces of a more ancient colonization of Europe by the species.