The advent of complete mitochondrial DNA (mtDNA) sequence data has ushered in a new phase of human evolutionary studies. Even quite limited volumes of complete mtDNA sequence data can now be used to identify the critical polymorphisms that define sub-clades within an mtDNA haplogroup, providing a springboard for large-scale high-resolution screening of human mtDNAs. This strategy has in the past been applied to mtDNA haplogroup V, which represents <5% of European mtDNAs. Here we adopted a similar approach to haplogroup H, by far the most common European haplogroup, which at lower resolution displayed a rather uninformative frequency distribution within Europe. Using polymorphism information derived from the growing complete mtDNA sequence database, we sequenced 1580 base pairs of targeted coding-region segments of the mtDNA genome in 649 individuals harboring mtDNA haplogroup H from populations throughout Europe, the Caucasus, and the Near East. The enhanced genealogical resolution clearly shows that sub-clades of haplogroup H have highly distinctive geographical distributions. The patterns of frequency and diversity suggest that haplogroup H entered Europe from the Near East approximately 20,000-25,000 years ago, around the time of the Last Glacial Maximum (LGM), and some sub-clades re-expanded from an Iberian refugium when the glaciers retreated approximately 15,000 years ago. This shows that a large fraction of the maternal ancestry of modern Europeans traces back to the expansion of hunter-gatherer populations at the end of the last Ice Age.