Far northeastern Siberia has been occupied by humans for more than 40 thousand years. Yet, owing to a scarcity of early archaeological sites and human remains, its population history and relationship to ancient and modern populations across Eurasia and the Americas are poorly understood. Here, we analyze 34 ancient genome sequences, including two from fragmented milk teeth found at the ~31.6 thousand-year- old (kya) Yana RHS site, the earliest northernmost Pleistocene human remains found to date. These genomes reveal the complex population dynamics in northeastern Siberia in the last 40,000 years, with evidence for at least three large-scale human migrations into the region. The first inhabitants, a previously unknown population represented by Yana RHS, which we name “Ancient North Siberians” (ANS), diverged ~38 kya from Western Eurasians, soon after the latter split from East Asians. Between 20 and 11 kya, the ANS population was largely replaced by peoples with East Asian-related ancestry. This newly-founded population contributed genetically to ancestral Native Americans and a group here named “Ancient Paleosiberians” (AP), represented by a 9.8 kya individual from Kolyma River. AP were closely related to the Siberian ancestors of Native Americans, and ancestral to contemporary communities such as Koryaks and Itelmen. Paleoclimatic modelling shows evidence for a refugium during the last glacial maximum (LGM) in southeastern Beringia, indicating Beringia as a possible location for the admixture forming both ancestral Native Americans and AP. Between 11 and 4 kya, AP were in turn largely replaced by another group of peoples with East Asian ancestry, the “Neosiberians” from which many contemporary Siberians derive. We detect gene flow events in both directions across the Bering Strait during this time, influencing the genetic composition of Inuit, as well as Na Dene-speaking Northern Native Americans, whose Siberian-related ancestry components is closely related to AP. Our analyses provide unique insights into the dynamic history of northeastern Siberian populations since the late Pleistocene, from the early colonisation of the region by modern humans, to the early expansion of post-glacial hunter-gatherers from LGM refugia, to the later expansion of East Asian Holocene groups. Each of these population expansions nearly replaced earlier inhabitants, generating a mosaic genetic signature in the make-up peoples today across the Americas and northern Eurasia, from Siberia to Scandinavia.