Interpretations of genetic data concerning the prehistory of Europe have long been a subject of great debate, but increasing amounts of ancient and modern DNA data are now providing new and more informative evidence. Y-chromosome resequencing studies in Europe have highlighted the prevalence of recent expansions of male lineages, and focused interest on the Bronze Age as a period of cultural and demographic change. These findings contrast with phylogeographic studies based on mitochondrial DNA (mtDNA), which have been interpreted as supporting expansions from glacial refugia. Here we have undertaken a population-based resequencing of complete mitochondrial genomes in Europe and the Middle East, in 340 samples from 17 populations for which Y-chromosome sequence data are also available. Demographic reconstructions show no signal of Bronze Age expansion, but evidence of Paleolithic expansions in all populations except the Saami, and with an absence of detectable geographical pattern. In agreement with previous inference from modern and ancient DNA data, the unbiased comparison between the mtDNA and Y-chromosome population datasets emphasizes the sex-biased nature of recent demographic transitions in Europe.