The Maghreb is a key region for understanding the dynamics of cattle dispersal and admixture with local aurochs following their earliest domestication in the Fertile Crescent more than 10,000 years ago. Here, we present data on autosomal genomes and mitogenomes obtained for four archaeological specimens of Iron Age (∼2,800 cal BP–2,000 cal BP) domestic cattle from the Eastern Maghreb, i.e. Althiburos (El Kef, Tunisia). D-loop sequences were obtained for an additional eight cattle specimens from this site. Maternal lineages were assigned to the elusive R and ubiquitous African-T1 haplogroups found in two and ten Althiburos specimens, respectively. Our results can be explained by post-domestication hybridization of Althiburos cattle with local aurochs. However, we cannot rule out an independent domestication in North Africa considering the shared ancestry of Althiburos cattle with the pre-domestic Moroccan aurochs and present-day African taurine cattle.