To fill remaining gaps in mitochondrial DNA diversity in the least surveyed eastern and western flanks of Siberia, 391 mtDNA samples (144 Tubalar from Altai, 87 Even from northeastern Siberia, and 160 Ulchi from the Russian Far East) were characterized via high-resolution restriction fragment length polymorphism/single nucleotide polymorphisms analysis. The subhaplogroup structure was extended through complete sequencing of 67 mtDNA samples selected from these and other related native Siberians. Specifically, we have focused on the evolutionary histories of the derivatives of M and N haplogroups, putatively reflecting different phases of settling Siberia by early modern humans. Population history and phylogeography of the resulting mtDNA genomes, combined with those from previously published data sets, revealed a wide range of tribal- and region-specific mtDNA haplotypes that emerged or diversified in Siberia before or after the last glacial maximum, ∼18 kya. Spatial distribution and ages of the “east” and “west” Eurasian mtDNA haploclusters suggest that anatomically modern humans that originally colonized Altai derived from macrohaplogroup N and came from Southwest Asia around 38,000 years ago. The derivatives of macrohaplogroup M, which largely emerged or diversified within the Russian Far East, came along with subsequent migrations to West Siberia millennia later. The last glacial maximum played a critical role in the timing and character of the settlement of the Siberian subcontinent.