Now extinct, the aurochs (Bos primigenius) was a keystone species in prehistoric Eurasian and North African ecosystems, and the progenitor of cattle (Bos taurus), domesticates that have provided people with food and labour for millennia1. Here we analysed 38 ancient genomes and found 4 distinct population ancestries in the aurochs-European, Southwest Asian, North Asian and South Asian-each of which has dynamic trajectories that have responded to changes in climate and human influence. Similarly to Homo heidelbergensis, aurochsen first entered Europe around 650 thousand years ago2, but early populations left only trace ancestry, with both North Asian and European B. primigenius genomes coalescing during the most recent glaciation. North Asian and European populations then appear separated until mixing after the climate amelioration of the early Holocene. European aurochsen endured the more severe bottleneck during the Last Glacial Maximum, retreating to southern refugia before recolonizing from Iberia. Domestication involved the capture of a small number of individuals from the Southwest Asian aurochs population, followed by early and pervasive male-mediated admixture involving each ancestral strain of aurochs after domestic stocks dispersed beyond their cradle of origin.