History of horse domestication remains poorly understood. On the basis of current evidence from archaeology, mitochondrial DNA, and Y-chromosomal sequencing, a number of different domestication scenarios have been proposed, ranging from the spread of domestic horses out of a restricted primary area of domestication to the domestication of numerous distinct wild horse populations. In this paper, we reconstruct both the population genetic structure of the extinct wild progenitor of domestic horses, Equus ferus, and the origin and spread of horse domestication in the Eurasian steppes by fitting a spatially explicit stepping-stone model to genotype data from >300 horses sampled across northern Eurasia. We find strong evidence for an expansion of E. ferus out of eastern Eurasia about 160 kya, likely reflecting the colonization of Eurasia by this species. Our best-fitting scenario further suggests that horse domestication originated in the western part of the Eurasian steppe and that domestic herds were repeatedly restocked with local wild horses as they spread out of this area. By showing that horse domestication was initiated in the western Eurasian steppe and that the spread of domestic herds across Eurasia involved extensive introgression from the wild, the Q:7 scenario of horse domestication proposed here unites evidence from archaeology, mitochondrial DNA, and Y-chromosomal DNA.