The extinct aurochs (Bos primigenius primigenius) was a large type of cattle that ranged over almost the whole Eurasian continent. The aurochs is the wild progenitor of modern cattle, but it is unclear whether European aurochs contributed to this process. To provide new insights into the demographic history of aurochs and domestic cattle, we have generated high-confidence mitochondrial DNA sequences from 59 archaeological skeletal finds, which were attributed to wild European cattle populations based on their chronological date and/or morphology. All pre-Neolithic aurochs belonged to the previously designated P haplogroup, indicating that this represents the Late Glacial Central European signature. We also report one new and highly divergent haplotype in a Neolithic aurochs sample from Germany, which points to greater variability during the Pleistocene. Furthermore, the Neolithic and Bronze Age samples that were classified with confidence as European aurochs using morphological criteria all carry P haplotype mitochondrial DNA, suggesting continuity of Late Glacial and Early Holocene aurochs populations in Europe. Bayesian analysis indicates that recent population growth gives a significantly better fit to our data than a constant-sized population, an observation consistent with a postglacial expansion scenario, possibly from a single European refugial population. Previous work has shown that most ancient and modern European domestic cattle carry haplotypes previously designated T. This, in combination with our new finding of a T haplotype in a very Early Neolithic site in Syria, lends persuasive support to a scenario whereby gracile Near Eastern domestic populations, carrying predominantly T haplotypes, replaced P haplotype-carrying robust autochthonous aurochs populations in Europe, from the Early Neolithic onward. During the period of coexistence, it appears that domestic cattle were kept separate from wild aurochs and introgression was extremely rare.