Archaeogenomic studies have largely elucidated human population history in West Eurasia during the Stone Age. However, despite being a broad geographical region of significant cultural and linguistic diversity, little is known about the population history in North Asia. We present complete mitochondrial genome sequences together with stable isotope data for 41 serially sampled ancient individuals from North Asia, dated between c. 13,790 BP and c. 1,380 BP extending from the Palaeolithic to the Iron Age. Analyses of mitochondrial DNA sequences and haplogroup data of these individuals revealed the highest genetic affinity to present-day North Asian populations of the same geographical region suggesting a possible long-term maternal genetic continuity in the region. We observed a decrease in genetic diversity over time and a reduction of maternal effective population size (Ne) approximately seven thousand years before present. Coalescent simulations were consistent with genetic continuity between present day individuals and individuals dating to 7,000 BP, 4,800 BP or 3,000 BP. Meanwhile, genetic differences observed between 7,000 BP and 3,000 BP as well as between 4,800 BP and 3,000 BP were inconsistent with genetic drift alone, suggesting gene flow into the region from distant gene pools or structure within the population. These results indicate that despite some level of continuity between ancient groups and present-day populations, the region exhibits a complex demographic history during the Holocene.