Background Genetic studies support the scenario that Bos taurus domestication occurred in the Near East during the Neolithic transition about 10 thousand years (ky) ago, with the likely exception of a minor secondary event in Italy. However, despite the proven effectiveness of whole mitochondrial genome data in providing valuable information concerning the origin of taurine cattle, until now no population surveys have been carried out at the level of mitogenomes in local breeds from the Near East or surrounding areas. Egypt is in close geographic and cultural proximity to the Near East, in particular the Nile Delta region, and was one of the first neighboring areas to adopt the Neolithic package. Thus, a survey of mitogenome variation of autochthonous taurine breeds from the Nile Delta region might provide new insights on the early spread of cattle rearing outside the Near East. Methodology Using Illumina high-throughput sequencing we characterized the mitogenomes from two cattle breeds, Menofi (N = 17) and Domiaty (N = 14), from the Nile Delta region. Phylogenetic and Bayesian analyses were subsequently performed. Conclusions Phylogenetic analyses of the 31 mitogenomes confirmed the prevalence of haplogroup T1, similar to most African cattle breeds, but showed also high frequencies for haplogroups T2, T3 and Q1, and an extremely high haplotype diversity, while Bayesian skyline plots pointed to a main episode of population growth ∼12.5 ky ago. Comparisons of Nile Delta mitogenomes with those from other geographic areas revealed that (i) most Egyptian mtDNAs are probably direct local derivatives from the founder domestic herds which first arrived from the Near East and the extent of gene flow from and towards the Nile Delta region was limited after the initial founding event(s); (ii) haplogroup Q1 was among these founders, thus proving that it underwent domestication in the Near East together with the founders of the T clades.