The contribution of domestic cattle in human societies is enormous, making cattle, along with other essential benefits, the economically most important domestic animal in the world today. To expand existing knowledge on cattle domestication and mitogenome diversity, we performed a comprehensive complete mitogenome analysis of the species (802 sequences, 114 breeds). A large sample was collected in South-east Europe, an important agricultural gateway to Europe during Neolithization and a region rich in cattle biodiversity. We found 1725 polymorphic sites (810 singletons, 853 parsimony-informative sites and 57 indels), 701 unique haplotypes, a haplotype diversity of 0.9995 and a nucleotide diversity of 0.0015. In addition to the dominant T3 and several rare haplogroups (Q, T5, T4, T2 and T1), we have identified maternal line in Austrian Murbodner cattle that possess surviving aurochs' mitochondria haplotype P1 that diverged prior to the Neolithization process. This is convincing evidence for rare female-mediated adaptive introgression of wild aurochs into domesticated cattle in Europe. We revalidated the existing haplogroup classification and provided Bayesian phylogenetic inference with a more precise estimated divergence time than previously available. Occasionally, classification based on partial mitogenomes was not reliable; for example, some individuals with haplogroups P and T5 were not recognized based on D-loop information. Bayesian skyline plot estimates (median) show that the earliest population growth began before domestication in cattle with haplogroup T2, followed by Q (~10.0-9.5 kyBP), whereas cattle with T3 (~7.5 kyBP) and T1 (~3.0-2.5 kyBP) expanded later. Overall, our results support the existence of interactions between aurochs and cattle during domestication and dispersal of cattle in the past, contribute to the conservation of maternal cattle diversity and enable functional analyses of the surviving aurochs P1 mitogenome.