Phylogenetic and diversity analysis of the mtDNA control region sequence variation of 821 individuals from Europe and the Middle East distinguishes five major lineage groups with different internal diversities and divergence times. Consideration of the diversities and geographic distribution of these groups within Europe and the Middle East leads to the conclusion that ancestors of the great majority of modern, extant lineages entered Europe during the Upper Paleolithic. A further set of lineages arrived from the Middle East much later, and their age and geographic distribution within Europe correlates well with archaeological evidence for two culturally and geographically distinct Neolithic colonization events that are associated with the spread of agriculture. It follows from this interpretation that the major extant lineages throughout Europe predate the Neolithic expansion and that the spread of agriculture was a substantially indigenous development accompanied by only a relatively minor component of contemporary Middle Eastern agriculturalists. There is no evidence of any surviving Neanderthal lineages among modern Europeans.