The newly appreciated importance of the human microbiome raises many questions as to its origin, evolution, and changing ecology. The application of advanced genomic and proteomic sequencing technologies to ancient human microbiomes, such as coprolites (paleofeces) and dental calculus (calcified plaque), as well as to contemporary microbiomes in traditional and industrialized societies, allows us to advance understanding of the evolutionary history of our microbial self and its impact on human health today.