Recent ancient DNA studies have revealed that the genetic history of modern Europeans was shaped by a series of migration and admixture events between deeply diverged groups. While these events are well described in Central and Southern Europe, genetic evidence from Northern Europe surrounding the Baltic Sea is still sparse. Here we report genome-wide DNA data from 24 ancient North Europeans ranging from ~7,500 to 200 calBCE spanning the transition from a hunter-gatherer to an agricultural lifestyle, as well as the adoption of bronze metallurgy. We show that Scandinavia was settled after the retreat of the glacial ice sheets from a southern and a northern route, and that the first Scandinavian Neolithic farmers derive their ancestry from Anatolia 1000 years earlier than previously demonstrated. The range of Western European Mesolithic hunter-gatherers extended to the east of the Baltic Sea, where these populations persisted without gene-flow from Central European farmers until around 2,900 calBCE when the arrival of steppe pastoralists introduced a major shift in economy and established wide-reaching networks of contact within the Corded Ware Complex.