Archaeological evidence from the last 8,000 years indicates that early African food-producing societies relied predominantly on livestock, particularly cattle, rather than crops. Cattle have since remained central to economies ranging from sedentary farming to mobile pastoralism across diverse ecosystems. The widespread use and persistence of cattle across Africa likely reflects their admixed ancestry, combining African taurine (Bos taurus), indicine (Bos indicus), and European taurine lineages, which were introduced at different times over the last ~8,000 years. To determine how varied human livelihood patterns and environmental factors affected the geographic distribution of these ancestries, we generated whole-genome sequences from 1,392 African cattle within a combined dataset of ~4,900 genomes, including two ancient genomes, one from Great Zimbabwe (~750 years old) and one from the Western Cape (~280 years old). Using local ancestry inference, we show that taurine and indicine lineages, despite co-existing in the same genomes for over a millennium, have followed markedly different trajectories: taurine ancestry is strongly structured geographically, maintained by sedentary communities under local selection; indicine ancestry is poorly geographically structured which likely reflects dispersal through pastoralist movement; and European taurine heritage is highly localised in South Africa where it is associated with strong selection for beef cattle. Together, these results reframe African cattle as carriers of co-resident lineages, each preserving a distinct record of human subsistence strategy, ecological constraint, and adaptive evolution.