The evolutionary origins of the bacterial lineages that populate the human gut are unknown. Here we show that multiple lineages of the predominant bacterial taxa in the gut arose via cospeciation with humans, chimpanzees, bonobos, and gorillas over the past 15 million years. Analyses of strain-level bacterial diversity within hominid gut microbiomes revealed that clades of Bacteroidaceae and Bifidobacteriaceae have been maintained exclusively within host lineages across hundreds of thousands of host generations. Divergence times of these cospeciating gut bacteria are congruent with those of hominids, indicating that nuclear, mitochondrial, and gut bacterial genomes diversified in concert during hominid evolution. This study identifies human gut bacteria descended from ancient symbionts that speciated simultaneously with humans and the African apes.