The driving force behind the transition from a foraging to a farming lifestyle in prehistoric Europe (Neolithization) has been debated for more than a century [1-3]. Of particular interest is whether population replacement or cultural exchange was responsible [3-5]. Scandinavia holds a unique place in this debate, for it maintained one of the last major hunter-gatherer complexes in Neolithic Europe, the Pitted Ware culture [6]. Intriguingly, these late hunter-gatherers existed in parallel to early farmers for more than a millennium before they vanished some 4,000 years ago [7, 8]. The prolonged coexistence of the two cultures in Scandinavia has been cited as an argument against population replacement between the Mesolithic and the present [7, 8]. Through analysis of DNA extracted from ancient Scandinavian human remains, we show that people of the Pitted Ware culture were not the direct ancestors of modern Scandinavians (including the Saami people of northern Scandinavia) but are more closely related to contemporary populations of the eastern Baltic region. Our findings support hypotheses arising from archaeological analyses that propose a Neolithic or post-Neolithic population replacement in Scandinavia [7]. Furthermore, our data are consistent with the view that the eastern Baltic represents a genetic refugia for some of the European hunter-gatherer populations.