Wild horses thrived across Eurasia until the Last Glacial Maximum to collapse after the beginning of the Holocene. The interplay of climate change, species adaptability to different environments, and human domestication in horse history is still lacking coherent continental-scale analysis integrating different lines of evidence. We assembled temporal and geographical information on 3070 horse occurrences across Eurasia, frequency data for 1120 archeological layers in Europe, and matched them to paleoclimatic and paleoenvironmental simulations for the Late Quaternary. Climate controlled the distribution of horses, and they inhabited regions in Europe and Asia with different climates and ecosystem productivity, suggesting plasticity to populate different environments. Their decline in Europe during the Holocene appears associated with an increasing loss and fragmentation of open habitats. Europe was the most likely source for the spread of horses toward more temperate regions, and we propose both Iberia and central Asia as potential centers of domestication.