The mtDNA polymorphism in representatives of various archaeological cultures of the Developed Bronze Age, Early Scythian, and Hunnish-Sarmatian periods was analyzed (N = 34). It detected the dominance of Western-Eurasian haplotypes (70.6%) in mtDNA samples from the representatives of the ancient population of the Early Bronze Age–Iron Age on the territory of Altai Mountains. Since the 8th to the 7th centuries BC, a sharp increase was revealed in the Eastern Eurasian haplogroups A, D, C, and Z (43.75%) as compared to previous cultures (16.7%). The presence of haplotype 223-242-290-319 of haplogroup A8 in Dolgans, Itelmens, Evens, Koryaks, and Yakuts indicates the possible long-term presence of its carriers in areas inhabited by these populations. The prevalence of western Eurasian haplotypes is observed not only in the Altai Mountains but also in Central Asia (Kazakhstan) and the south of the Krasnoyarsk Krai. All of the three studied samples from the Western Eurasian haplogroups were revealed to contain U, H, T, and HV. The ubiquitous presence of haplotypes of haplogroup H and some haplogroups of cluster U (U5a1, U4, U2e, and K) in the vast territory from the Yenisei River basin to the Atlantic Ocean may indicate the direction of human settlement, which most likely occurred in the Paleolithic Period from Central Asia.