Very recently, we discovered a vast new microbial self: the human microbiome. Our native microbiota interface with our biology and culture to influence our health, behavior, and quality of life, and yet we know very little about their origin, evolution, or ecology. With the advent of industrialization, globalization, and modern sanitation, it is intuitive that we have changed our relationship with microbes, but we have little information about the ancestral state of our microbiome, and we therefore lack a foundation for characterizing this change. High-throughput sequencing has opened up new opportunities in the field of paleomicrobiology, allowing us to investigate the evolution of the complex microbial ecologies that inhabit our bodies. By focusing on recent coprolite and dental calculus research, we explore how emerging research on ancient human microbiomes is changing the way we think about ancient disease and how archaeological studies can contribute to a medical understanding of health and nutrition today.