How host-associated microbial communities evolve as their hosts diversify remains equivocal: how conserved is their composition? What was the composition of ancestral microbiota? Do microbial taxa covary in abundance over millions of years? Multivariate phylogenetic models of trait evolution are key to answering similar questions for complex host phenotypes, yet they are not directly applicable to relative abundances, which usually characterize microbiota. Here, we extend these models in this context, thereby providing a powerful approach for estimating phylosymbiosis (the extent to which closely related host species harbor similar microbiota), ancestral microbiota composition, and integration (evolutionary covariations in bacterial abundances). We apply our model to the gut microbiota of mammals and birds. We find significant phylosymbiosis that is not entirely explained by diet and geographic location, indicating that other evolutionary-conserved traits shape microbiota composition. We identify main shifts in microbiota composition during the evolution of the two groups and infer an ancestral mammalian microbiota consistent with an insectivorous diet. We also find remarkably consistent evolutionary covariations among bacterial orders in mammals and birds. Surprisingly, despite the substantial variability of present-day gut microbiota, some aspects of their composition are conserved over millions of years of host evolutionary history.