Domestic cattle have a key economic role in African societies, providing an important source of mobile wealth through supply of meat, milk, cowhide, fuel, transport, and traction. The phenotypic diversity of African cattle reflects adaptation to a wide range of agroecological conditions and complex patterns of admixture between the humpless Bos taurus (taurine) and humped Bos indicus (zebu) subspecies, which share a common ancestor 150-500 thousand years ago. Human migration and trade from Asia have left a peak of zebu nuclear ancestry in East Africa and most cattle populations across the continent have a hybrid genetic composition. Notwithstanding this, all African cattle possess taurine mitochondrial haplotypes, even populations with significant zebu nuclear ancestry. In this regard, the efficient functioning of the mitochondrion relies on a network of biochemical interactions between the products of 37 mitochondrial genes and more than one thousand nuclear genes; therefore, admixed African cattle represent ideal populations for evaluating mitonuclear interactions and mismatch between the nuclear and mitochondrial genomes. Using high-density SNP array data from 18 different cattle populations, including ten African admixed breeds, we find strong evidence for mitonuclear coevolution in hybrid African cattle with significant retention of Bos taurus alleles at mitochondrially-targeted nuclear genes, particularly those genes with products that directly interact with mtDNA-encoded protein subunits in OXPHOS and ribosomal complexes, or that have functions in mtDNA replication. We also show that subspecific local ancestry varies substantially across the genomes of admixed populations, with a marked signal of taurine ancestry at the major histocompatibility (MHC) gene cluster, which likely reflects adaptation to infectious disease challenges facing African livestock. Our results demonstrate that African admixed cattle represent an excellent comparative model for studying the phenotypic consequences of mitonuclear mismatch and genomic introgression in humans and other large mammals.