Mammals harbor diverse gut microbiomes (GMs) that perform critical functions for host health and fitness. Identifying factors associated with GM variation can help illuminate the role of microbial symbionts in mediating host ecological interactions and evolutionary processes, including diversification and adaptation. Many mammals demonstrate phylosymbiosis-a pattern in which more closely-related species harbor more similar GMs-while others show overwhelming influences of diet and habitat. Here, we generated 16S rRNA sequence data from fecal samples of 15 species of wild lemurs across southern Madagascar to (1) test a hypothesis of phylosymbiosis, and (2) test trait correlations between dietary guild, habitat, and GM diversity. Our results provide strong evidence of phylosymbiosis, though some closely-related species with substantial ecological niche overlap exhibited greater GM similarity than expected under Brownian motion. Phylogenetic regressions also showed a significant correlation between dietary guild and UniFrac diversity, but not Bray-Curtis or Jaccard. This discrepancy between beta diversity metrics suggests that older microbial clades have stronger associations with diet than younger clades, as UniFrac weights older clades more heavily. We conclude that GM diversity is predominantly shaped by host phylogeny, and that microbes associated with diet were likely acquired before evolutionary radiations within the lemur families examined.