Mammals are metagenomic in that they are composed of not only their own gene complements but also those of all of their associated microbes. To understand the coevolution of the mammals and their indigenous microbial communities, we conducted a network-based analysis of bacterial 16S ribosomal RNA gene sequences from the fecal microbiota of humans and 59 other mammalian species living in two zoos and in the wild. The results indicate that host diet and phylogeny both influence bacterial diversity, which increases from carnivory to omnivory to herbivory; that bacterial communities codiversified with their hosts; and that the gut microbiota of humans living a modern life-style is typical of omnivorous primates.