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.IMPORTANCE In this comprehensive survey of microbiomes of >900 species, including 315 mammals and 491 birds, we find a striking convergence of the microbiomes of birds and animals that fly. In nonflying mammals, diet and short-term evolutionary relatedness drive the microbiome, and many microbial species are specific to a particular kind of mammal, but flying mammals and birds break this pattern with many microbes shared across different species, with little correlation either with diet or with relatedness of the hosts. This finding suggests that adaptation to flight breaks long-held relationships between hosts and their microbes.