The Altai region is a crossroads of the Asian steppes. However, the population history of the region remains understudied. We analyse ancient human genomes from the Altai and Ob regions, creating a ca. 1400-year-long time transect with 91 new data. We demonstrate an Iron Age genetic variety that continued into the Medieval era, with additional large-scale spread of East Asian genetic ancestry coinciding with the rise and spread of the Turkic cultural customs. Furthermore, we find a unique lineage in the Early Medieval Altai with elevated Ancient North Eurasian ancestry, providing a missing link between the North Eurasian hunter-gatherers and modern North Asian people. We identify distinct genetic patterns and connections among populations of the Mountainous and the Forest-Steppe Altai in the 4th-8th centuries.