Animal hosts have evolved intricate associations with microbial symbionts, where both depend on each other for particular functions. In many cases, these associations lead to phylosymbiosis, where phylogenetically related species harbour compositionally more similar microbiomes than distantly related species. However, evidence for phylosymbiosis is either weak or lacking in gut microbiomes of flying vertebrates, particularly in birds. To shed more light on this phenomenon, we compared cloacal microbiomes of 37 tropical passerine bird species from New Guinea using 16S rRNA bacterial gene sequencing. We show a lack of phylosymbiosis and document highly variable microbiomes. Furthermore, we find that gut bacterial community compositions are species-specific and tend to be shaped by host diet but not sampling locality, potentially driven by the similarities in habitats used by individual species. We further show that flight-associated gut modifications, coupled with individual dietary differences, shape gut microbiome structure and variation, contributing to the lack of phylosymbiosis. These patterns indicate that the stability of symbiosis may depend on microbial functional diversity rather than taxonomic composition. Furthermore, the more variable and fluid host-microbe associations suggest probable disparities in the potential for coevolution between bird host species and microbial symbionts.