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.