A Neolithic domestication of taurine cattle in the Fertile Crescent from local aurochsen (Bos primigenius) is generally accepted, but a genetic contribution from European aurochsen has been proposed. Here we performed a survey of a large number of taurine cattle mitochondrial DNA (mtDNA) control regions from numerous European breeds confirming the overall clustering within haplogroups (T1, T2 and T3) of Near Eastern ancestry, but also identifying eight mtDNAs (1.3%) that did not fit in haplogroup T. Sequencing of the entire mitochondrial genome showed that four mtDNAs formed a novel branch (haplogroup R) which, after the deep bifurcation that gave rise to the taurine and zebuine lineages, constitutes the earliest known split in the mtDNA phylogeny of B. primigenius. The remaining four mtDNAs were members of the recently discovered haplogroup Q. Phylogeographic data indicate that R mtDNAs were derived from female European aurochsen, possibly in the Italian Peninsula, and sporadically included in domestic herds. In contrast, the available data suggest that Q mtDNAs and T subclades were involved in the same Neolithic event of domestication in the Near East. Thus, the existence of novel (and rare) taurine haplogroups highlights a multifaceted genetic legacy from distinct B. primigenius populations. Taking into account that the maternally transmitted mtDNA tends to underestimate the extent of gene flow from European aurochsen, the detection of the R mtDNAs in autochthonous breeds, some of which are endangered, identifies an unexpected reservoir of genetic variation that should be carefully preserved.