Microbial communities within the mammalian gut endow their hosts with properties they did not have to evolve on their own. How these communities are selected, assembled and maintained is enigmatic. We have obtained >30,000 bacterial 16S rRNA gene sequences from the gut microbiota of ~60 species of mammals and marsupials. Fecal samples were collected from animals residing in the San Diego and St Louis Zoos, and in the wild in Namibia, Mongolia and the USA. Generally, host diet is a strong predictor of microbial community diversity which falls into three broad groups that correspond to herbivores, omnivores, and carnivores. The stable isotope signatures of feces, which are markers for trophic level, explain much of the observed variation.  Because mammalian diets tend to track mammalian phylogeny, to tease apart the impact of diet vs. the evolutionary history on microbial diversity, we examined mammals whose diets are unusual for their lineage. These exceptions reveal two different patterns that may represent parallel and convergent evolution in gut microbiota functionality: (i) primates that specialize in high cellulose diets harbor communities that are more similar to those of strict herbivores than to other primates, indicating that the same bacterial lineages perform the same functions in those unrelated animals; (ii) pandas harbor communities that are similar to other bears, implying that a different suite of bacterial lineages took on folivory. We hypothesize that a shift to a specialized diet in primates is likely to be accompanied by an increase in the fraction of the community, already present, that can breakdown key components of the new diet. In contrast, adoption by bears of an herbivorous lifestyle occurred even though the bacterial lineages in the gut stayed constant: therefore, it is likely that the gene content of the bacterial genomes changed to confer a new, folivorous functionality.