Author summary The Scandinavian peninsula was the last part of Europe to be colonized after the Last Glacial Maximum. The migration routes, cultural networks, and the genetic makeup of the first Scandinavians remain elusive and several hypotheses exist based on archaeology, climate modeling, and genetics. By analyzing the genomes of early Scandinavian hunter-gatherers, we show that their migrations followed two routes: one from the south and another from the northeast along the ice-free Norwegian Atlantic coast. These groups met and mixed in Scandinavia, creating a population more diverse than contemporaneous central and western European hunter-gatherers. As northern Europe is associated with cold and low light conditions, we investigated genomic patterns of adaptation to these conditions and genes known to be involved in skin pigmentation. We demonstrate that Mesolithic Scandinavians had higher levels of light pigmentation variants compared to the respective source populations of the migrations, suggesting adaptation to low light levels and a surprising signal of genetic continuity in TMEM131, a gene that may be involved in long-term adaptation to the cold.