Recent ancient DNA studies have provided new evidence for prehistoric population structure associated with the contentious transition to an agricultural lifestyle in Europe. In this study, we infer human population structure and history in Holocene Europe by generating ancient genomic sequence data from 9 Scandinavian individuals associated with the foraging Pitted Ware Culture and the agricultural Funnel Beaker Culture (TRB). We obtained up to 1.1x coverage of the genomes for the nine individuals allowing direct comparisons of the two groups. We show that the Neolithic Scandinavian individuals show remarkable population structure corresponding to their cultural association. Looking beyond Scandinavia, we integrate this data with ancient genomes from Southern Europe and find that the Tyrolean Iceman from an agricultural context is most similar to Scandinavian individuals from a farming context, whereas Mesolithic Iberian hunter-gatherers are most similar to Scandinavian hunter-gatherers, opposite to what would have been predicted from their geographical origins. This finding shows that among these individuals, lifestyle is the major determinant of genetic ancestry rather than geography. Comparisons with modern populations reveal a latitudinal relationship where Southern European populations such as Sardinians are closely related with the genetic variation of the agricultural groups, whereas hunter-gatherer individuals appear to have the closest relationship with Baltic populations such as Lithuanians and present-day Scandinavians. Our results also demonstrate that while Middle Eastern populations are not the most similar to Neolithic farmers, this observation can be explained by African-related admixture in more recent times for Middle Eastern groups, which, once accounted for, reveals that the other major component of their ancestry resembles Neolithic farmers. While present-day Scandinavian populations are intermediate between the two groups, consistent with admixture, they appear genetically slightly closer to Neolithic hunter-gatherers than Neolithic farmers. This suggests a model where initial colonization by agricultural populations was followed by later admixture with hunter-gatherer populations or gene flow from other regions.