From the paper:
Human evolutionary history includes all the complex demographic, natural selection, and stochastic processes that have shaped our species. Despite the limitations of genetic and archaeological data to inform on all the details of human evolution, they constitute an irreplaceable source of information to appraise the key episodes that are likely to have had major impacts on patterns of genetic, morphological, and cultural variation. When considering AMH in Europe, three such critical periods are apparent: (i) the expansion of AMH out of Africa and their colonization of Europe approximately 45 000 years ago (45 ka), (ii) the last glacial maximum (LGM) and the formation of uninhabitable areas in Europe between 27 and 16 ka, and (iii) the arrival of Neolithic culture in southeast Europe and its spread throughout the rest of the continent between 9 and 5 ka. Here we review genetic evidence describing these major demographic episodes in the context of archaeological and chronological data.I have postulated that there was at least one important post-5ka event affecting Europe. But, in order to understand how events played out before 5ka and the present, we must first understand the background of what was taking place in Europe before 5ka.
On the earliest settlement of Europe:
Until recently, the earliest date for the first appearance of AMH in Europe had been set to around 42 to 43 ka solely based on their proposed association with Aurignacian artifacts (Table 1) [5,6]. New direct radiocarbon dates of fossils support this view and indicate that AMH appeared in Europe by 44.2– 41.5 calibrated (cal.) ka BP at Kent’s Cavern in southern England  and by 45–43 cal. ka BP in Grotta del Cavallo, Italy , whereas Neanderthals did not survive in most of Europe and the Caucasus after 39 cal. ka BP [8,9].These dates are so close to the MP/UP transition in the Levant (49-46 cal ky BP), with the Aurignacian appearing shortly thereafter in both Central Europe and Italy. It would appear that modern humans swiftly colonized Europe after they made the crucial UP leap. Of course, in my opinion, this population was ultimately descended from inhabitants of Arabia, escaping post-70ka climatic deterioration and pre-100ka with the archaeologically attested Nubian Complex. But, in any case, it is probably the last crucial step, when humans went into warp drive post-50ka that led to the first modern human colonization of Europe and ultimately the extinction (or absorption?) of the Neandertals.
But, the early colonizers were in for a rough patch of climate that last for several millennia, making whole parts of Europe uninhabitable, and allowing few ones to survive in the south of the continent:
After the disappearance of the Neanderthals and particularly during the LGM, the northern parts of Europe were covered by ice sheets, leaving humans to survive in poorly resourced environments [10,11]. Parts of northern Europe were either completely abandoned  or sparsely populated . The archaeological record of this period catalogs a complex series of interrelated material cultures that vary in their geographic ranges and temporal durations (Table 1). Spatial patterns of material culture change have been interpreted as indicating colonization of regions up to 52 degrees N latitude during the Gravettian, followed by partial or complete retreat of most northern populations by 24 ka, and recolonization of these regions by 20–16 ka, with some continuity of occupation in more southern latitudes . However, the extent to which material cultures correspond to distinct human populations, and to which their distribu- tion changes through time correspond to demographic pro- cesses, remains unclear.The following table presents a very useful summary of archaeological developments in west Eurasia:
So far, we have substantial autosomal data of modern humans only from the Mesolithic onwards (Iberia), but also mtDNA from much older specimens of the Gravettian in Italy and Russia.
Apparently, other people are looking to extract ancient genomic DNA from older remains as well:
A group led by evolutionary geneticist Johannes Krause of the University of Tubingen, Germany, is trying to remove and reassemble nuclear DNA from the bones of roughly 20,000-year-old people in Europe. If successful, that effort will provide the first look at whether Stone Age humans carried more Neandertal genes than people today do. “It’s a completely open question whether more interbreeding occurred in the past than what we’ve found so far,” Krause says.But, let's see where things stand now.
Ancient mtDNA sequences recovered from three Upper Paleolithic and 14 Mesolithic and Neolithic hunter-gatherers all belong to the mtDNA haplogroup U , currently found at frequencies between 1 and 7% in most modern European populations, but at up to 20% in Baltic populations and around 40% in Saami. Interestingly, almost all pre-Neolithic hunter-gatherers from Central and
Northeastern Europesequenced to date, and the majority of European post-Neolithic hunter-gatherers, carry U-type mtDNA [48,49] (Figure 1a,c). There are three exceptions: two Italian individuals with N* and pre-HV types , and one from ; the latter dating to the late Neolithic and possibly being the result of an admix- ture event with incoming farmers. In all other hunter- gatherer samples, the now common mtDNA lineages H, T, K, and J are absent, suggesting that these mtDNA lineages were introduced during the Neolithic period. Sweden
The mtDNA evidence is indeed the strongest argument for large-scale population replacement during the Neolithic, a scenario which has found support by the sequencing of Neolithic hunter-gatherers from Gotland Sweden and Mesolithic ones from Iberia.
Europein times slices and depicting the locations from which ancient mitochondrial DNA (mtDNA) sequences were retrieved. Squares represent hunter-gatherer individuals and circles represent farming individuals. Lineages belonging to the U-clade are shown in red. Other lineages are shown in yellow. (a) Paleolithic and Mesolithic hunter-gatherers 13 500–8300 BP (plotted on a map of Europeduring the last glacial maximum ca 22 000 BP). All Pleistocene hunter-gatherers analyzed to date carry mitochondrial lineages that belong to one of the U-clades: U2, U4, or U5. (b) Early farmers 7600–6500 BP. The map illustrates the approximate arrival times and duration of the earliest Neolithic cultures (in years BP). Very few of the early farmers belong to one of the U-clade mtDNA haplotypes, indicating discontinuity between Paleolithic/Mesolithic hunter-gatherers and early farmers [48,64]. (c) Later hunter-gatherers 6500–4500 BP. Whereas early hunter-gatherers carry exclusively mitochondrial U-lineages, later hunter-gatherers show additional lineages that are also present in early farming groups (b), pointing to a possible admixture between the groups or a change in lifestyle of former farmers back to hunting-gathering in Northern Europe. (d) Later farmers 6500–4500 BP. Compared to the period of the first appearance of farmers, late farmers have a significantly higher frequency of U-lineages. This can be explained by increasing rates of admixture between farmer and hunter gatherer groups during this period and by the adoption of a farming lifestyle by hunter-gatherers. The maps are adapted from  and show datapoints from [46,48,51, 54–56,61,62,64,70,71]. Abbreviation: BP, before present.
And, of course, we have the ubiquitous Y-haplogroup G2a as the lineage par excellence of the first European farmers:
In contrast to mtDNA, ancient Y-chromosome data has until recently been less informative, but a single Y-chro-mosome haplotype (G2a) in 20 of 22 male individuals from the Late Neolithic cave site at Treilles  led to the hypothesis that a small male founding population arrived in Southern France, probably by a maritime route from the eastern Mediterranean, in the early Neolithic. The same haplotype was also found in five of six individuals from the Avellaner Cave  and in one out of three Central Euro-pean LBK individuals . If authentic, the presence of the Y-chromosome haplogroup G2a in 26 of 31 Neolithic individuals from Germany, France, and Spain is both surprising and intriguing, but this requires further examination.
The only high coverage genome sequence of a prehistoric European individual is that of the Tyrolean Iceman, Oetzi, a 5300 year-old individual from South Tyrol, which was recently reported at 7-fold coverage . Comparison with 1300 contemporary Europeans indicated closest genetic affinities with southern Europeans, particularly inhabi-tants of the Tyrrhenian Islands. Intriguingly, this is also the region where the Y-chromosome haplotype of the Ice-man is found at highest frequency, and this haplotype belongs to the same G2a haplogroup described above.
And of course:
Future research should also reveal the effects of post-Neolithic demographic processes, including migration events, which preliminary data suggest had a major impact upon the distribution of genetic variation. These include events associated with Bronze Age civilizations, Iron Age cultures, and later migrations, including those triggered by the rise and fall of Empires.
The recovery of the European past has only just begun.
Trends in Genetics doi:10.1016/j.tig.2012.06.006
The genetic history of Europeans
Ron Pinhasi, Mark G. Thomas, Michael Hofreiter, Mathias Currat, Joachim Burger
The evolutionary history of modern humans is characterized by numerous migrations driven by environmental change, population pressures, and cultural innovations. In Europe, the events most widely considered to have had a major impact on patterns of genetic diversity are the initial colonization of the continent by anatomically modern humans (AMH), the last glacial maximum, and the Neolithic transition. For some decades it was assumed that the geographical structuring of genetic diversity within Europe was mainly the result of gene flow during and soon after the Neolithic transition, but recent advances in next-generation sequencing (NGS) technologies, computer simulation modeling, and ancient DNA (aDNA) analyses are challenging this simplistic view. Here we review the current knowledge on the evolutionary history of humans in Europe based on archaeological and genetic data.