Humans and other primates harbour complex gut bacterial communities that influence health and disease, but the evolutionary histories of these symbioses remain unclear due to a lack of information about the state of the microbiota in ancestral primates. Here we show that hundreds of gut bacterial lineages co-diversified with primate species over millions of years, but that nearly half of these ancestral symbionts have been lost from humans. Analyses of thousands of metagenome-assembled genomes from humans, chimpanzees, bonobos, and other non-human primates revealed significant co-diversification within ten gut bacterial phyla. Remarkably, 44% of the co-diversifying clades detected in African apes were absent from available human metagenomic data. In contrast, only ~3% of the clades displaying the weakest evidence for co-diversification and detected in African apes were absent from humans. This study identifies bacterial symbioses that predate hominid diversification, revealing accelerated extinctions of ancestral, co-diversifying symbionts from human populations.