Naturally occurring admixture has now been documented in every major primate lineage, suggesting its key role in primate evolutionary history. Active primate hybrid zones can provide valuable insight into this process. Here, we investigate the history of admixture in one of the best-studied natural primate hybrid zones, between yellow baboons (Papio cynocephalus) and anubis baboons (Papio anubis) in the Amboseli ecosystem of Kenya. We generated a new genome assembly for yellow baboon and low-coverage genomewide resequencing data from yellow baboons, anubis baboons and known hybrids (n = 44). Using a novel composite likelihood method for estimating local ancestry from low-coverage data, we found high levels of genetic diversity and genetic differentiation between the parent taxa, and excellent agreement between genome-scale ancestry estimates and a priori pedigree, life history and morphology-based estimates (r(2) = 0.899). However, even putatively unadmixed Amboseli yellow individuals carried a substantial proportion of anubis ancestry, presumably due to historical admixture. Further, the distribution of shared vs. fixed differences between a putatively unadmixed Amboseli yellow baboon and an unadmixed anubis baboon, both sequenced at high coverage, is inconsistent with simple isolation-migration or equilibrium migration models. Our findings suggest a complex process of intermittent contact that has occurred multiple times in baboon evolutionary history, despite no obvious fitness costs to hybrids or major geographic or behavioural barriers. In combination with the extensive phenotypic data available for baboon hybrids, our results provide valuable context for understanding the history of admixture in primates, including in our own lineage.