Mitochondrial (mt) DNA D-loop heterogeneity, haplotype distribution and possible sub-population structures within the relevant populations are important for DNA-based traceability. To gain insight into this distribution, we compared 1515 Bos taurus mtDNA D-loop sequences available from GenBank to 219 sequences that we sequenced de novo. A pronounced ambiguous trace typical of C-track length heteroplasmy was encountered in 5% of the samples, which were excluded from the analysis. Previously undescribed mutations and haplotypes were observed in 6% and 63% of the sequences, respectively. B. taurus haplotypes divided into the taurus, indicus and grunniens types and 302 variable sites formed the 858 taurus haplotypes detected. Fifty-five sites displayed a complex level of variation. As each level represents an independent mutation event, a total of 399 mutations were traced, which could potentially explain independent formation of less than half (47%) of the haplotypes encountered: most haplotypes were derived from different combinations of these mutations. We suggest that a mutational hotspot may explain these results and discuss the usefulness of mtDNA for identity and maternity assurance.