Multiple factors over the lifetime of an individual, including diet, geography, and physiologic state, will influence the microbial communities within the primate gut. To determine the source of variation in the composition of the microbiota within and among species, we investigated the distal gut microbial communities harbored by great apes, as present in fecal samples recovered within their native ranges. We found that the branching order of host-species phylogenies based on the composition of these microbial communities is completely congruent with the known relationships of the hosts. Although the gut is initially and continuously seeded by bacteria that are acquired from external sources, we establish that over evolutionary timescales, the composition of the gut microbiota among great ape species is phylogenetically conserved and has diverged in a manner consistent with vertical inheritance.