Diet and host phylogeny drive the taxonomic and functional contents of the gut microbiome in mammals, yet it is unknown whether these patterns hold across all vertebrate lineages. Here, we assessed gut microbiomes from ∼900 vertebrate species, including 315 mammals and 491 birds, assessing contributions of diet, phylogeny, and physiology to structuring gut microbiomes. In most nonflying mammals, strong correlations exist between microbial community similarity, host diet, and host phylogenetic distance up to the host order level. In birds, by contrast, gut microbiomes are only very weakly correlated to diet or host phylogeny. Furthermore, while most microbes resident in mammalian guts are present in only a restricted taxonomic range of hosts, most microbes recovered from birds show little evidence of host specificity. Notably, among the mammals, bats host especially bird-like gut microbiomes, with little evidence for correlation to host diet or phylogeny. This suggests that host-gut microbiome phylosymbiosis depends on factors convergently absent in birds and bats, potentially associated with physiological adaptations to flight. Our findings expose major variations in the behavior of these important symbioses in endothermic vertebrates and may signal fundamental evolutionary shifts in the cost/benefit framework of the gut microbiome.