Interpreting the evolutionary history of bacterial communities within the human body (microbiome) is key to understanding multiple aspects of health and disease, and elucidating mechanisms that underlie bacterial and human co-evolution. Although research once suggested that the human microbiome evolved in accordance with the hominid evolutionary tree, recent evidence has indicated that the human microbiome underwent significant changes after the split between human and chimpanzee lineages. To examine this theory in greater detail, we recovered ancient bacterial DNA within dental calculus (calcified dental plaque) from Neandertals, ancient and present-day humans, and greater apes to determine the evolutionary history of the hominid microbiome. Similar bacterial community structures were detected in all non-agriculturalist specimens (Neandertals, chimpanzees, African and European hunter-gatherers), revealing the existence of a once shared hominid microbiome. In contrast, a marked change was observed in the oral microbiome when humans adopted agriculture in both Europe and Africa. Significant changes in the core oral microbiome were also observed during the agricultural and industrial revolutions, as well as the modern era, revealing factors that can significantly impact the human microbiome and alter the evolutionary signal associated between bacteria and humans. Consequently, essentially all present-day humans possess an evolutionarily recent oral microbiome that was introduced after the introduction of farming Europe, nearly 7,500 years ago. Lastly, this analysis revealed, for the first, time, pathogens and diseases shared between one of our most recent hominid ancestors (Neandertals) and modern humans, revealing long evolutionary histories for several key oral and respiratory pathogens. These ancient and historical samples allow us to identify the timing of cultural and environmental events that altered the relationship between humans and their microorganisms, which may have significant health consequences in the modern world.