Despite numerous descriptions about the interactions between Neandertals and anatomically modern humans, little is known about the diseases and microorganisms that were shared between these hominids. DNA sequencing of preserved dental plaque (calculus) from ancient hominid skeletons now provides a unique opportunity to examine the evolution of ancient diseases and commensal bacterial species (microbiota) through time. Exploring the past evolutionary history of microbiota is critical for modern human health, as alterations to these commensal species are now linked to many diseases, including obesity, diabetes, heart disease, and others. Using a shotgun sequencing approach, we obtained ancient bacterial DNA from 53 ancient dental calculus samples collected from chimpanzees, Neandertals, and ancient and modern humans. We reconstruct the first oral microbiota of an extinct species, and reveal nearly 200 bacterial species present in Neandertals, including some that are shared with modern humans today and are linked to tooth decay (Streptococcus mutans) and periodontal disease (Porphyromonas, Tanerella, and Treponema taxa). By comparing microbiota from Neandertal and a wide-range of ancient humans, we also reconstructed the evolutionary history of the human microbiota over the past 55,000 years. We observe a significant shift in ancient hunter-gatherer microbiota ~35,000 yBP in Europe and ~3,000 yBP in Africa, when the microbiota diverged from that shared amongst Neandertals, chimpanzees, and ancient humans. When ancient humans switched to agriculture, another significant change in microbiota was observed in both Europe and Africa. This change was demarked by an increase of Fusobacteria microorganisms linked to polymicrobial oral diseases, revealing why oral health significantly declined after ancient humans adopted agriculture. Together, this data from extinct and extant hominids over the last 55,000 years provides the first record of human microbiota evolution, and a means to understand why these bacterial communities are now linked to disease.