Mongolia is located in a strategic position at the eastern edge of the Eurasian Steppe. Nomadic populations moved across this wide area for millennia before developing more sedentary communities, extended empires, and complex trading networks, which connected western Eurasia and eastern Asia until the late Medieval period. We provided a fine-grained portrait of the mitochondrial DNA (mtDNA) variation observed in present-day Mongolians and capable of revealing gene flows and other demographic processes that took place in Inner Asia, as well as in western Eurasia. The analyses of a novel dataset (N = 2,420) of mtDNAs highlighted a clear matrilineal differentiation within the country due to a mixture of haplotypes with eastern Asian (EAs) and western Eurasian (WEu) origins, which were differentially lost and preserved. In a wider genetic context, the prevalent EAs contribution, larger in eastern and central Mongolian regions, revealed continuous connections with neighboring Asian populations until recent times, as attested by the geographically restricted haplotype-sharing likely facilitated by the Genghis Khan’s so-called Pax Mongolica. The genetic history beyond the WEu haplogroups, notably detectable on both sides of Mongolia, was more difficult to explain. For this reason, we moved to the analysis of entire mitogenomes (N = 147). Although it was not completely possible to identify specific lineages that evolved in situ, two major changes in the effective (female) population size were reconstructed. The more recent one, which began during the late Pleistocene glacial period and became steeper in the early Holocene, was probably the outcome of demographic events connected to western Eurasia. The Neolithic growth could be easily explained by the diffusion of dairy pastoralism, as already proposed, while the late glacial increase indicates, for the first time, a genetic connection with western Eurasian refuges, as supported by the unusual high frequency and internal sub-structure in Mongolia of haplogroup H1, a well-known post-glacial marker in Europe. Bronze Age events, without a significant demographic impact, might explain the age of some mtDNA haplogroups. Finally, a diachronic comparison with available ancient mtDNAs made it possible to link six mitochondrial lineages of present-day Mongolians to the timeframe and geographic path of the Silk Route.