Significance The microbiome plays key roles in human health, but little is known about its evolution. We investigate the evolutionary history of the African hominid oral microbiome by analyzing dental biofilms of humans and Neanderthals spanning the past 100,000 years and comparing them with those of chimpanzees, gorillas, and howler monkeys. We identify 10 core bacterial genera that have been maintained within the human lineage and play key biofilm structural roles. However, many remain understudied and unnamed. We find major taxonomic and functional differences between the oral microbiomes of Homo and chimpanzees but a high degree of similarity between Neanderthals and modern humans, including an apparent Homo -specific acquisition of starch digestion capability in oral streptococci, suggesting microbial coadaptation with host diet.