Despite much attention, history of sheep (Ovis aries) evolution, including its dating, demographic trajectory and geographic spread, remains controversial. To address these questions, we generated 45 complete and 875 partial mitogenomic sequences, and performed a meta-analysis of these and published ovine mitochondrial DNA sequences (n = 3,229) across Eurasia. We inferred that O. orientalis and O. musimon share the most recent female ancestor with O. aries at approximately 0.790 Ma (95% CI: 0.637-0.934 Ma) during the Middle Pleistocene, substantially predating the domestication event (∼8-11 ka). By reconstructing historical variations in effective population size, we found evidence of a rapid population increase approximately 20-60 ka, immediately before the Last Glacial Maximum. Analyses of lineage expansions showed two sheep migratory waves at approximately 4.5-6.8 ka (lineages A and B: ∼6.4-6.8 ka; C: ∼4.5 ka) across eastern Eurasia, which could have been influenced by prehistoric West-East commercial trade and deliberate mating of domestic and wild sheep, respectively. A continent-scale examination of lineage diversity and approximate Bayesian computation analyses indicated that the Mongolian Plateau region was a secondary center of dispersal, acting as a "transportation hub" in eastern Eurasia: Sheep from the Middle Eastern domestication center were inferred to have migrated through the Caucasus and Central Asia, and arrived in North and Southwest China (lineages A, B, and C) and the Indian subcontinent (lineages B and C) through this region. Our results provide new insights into sheep domestication, particularly with respect to origins and migrations to and from eastern Eurasia.