Gut bacteria can affect key aspects of host fitness, such as development, fecundity, and lifespan, while the host, in turn, shapes the gut microbiome. However, it is unclear to what extent individual species versus community interactions within the microbiome are linked to host fitness. Here, we combinatorially dissect the natural microbiome of Drosophila melanogaster and reveal that interactions between bacteria shape host fitness through life history tradeoffs. Empirically, we made germ-free flies colonized with each possible combination of the five core species of fly gut bacteria. We measured the resulting bacterial community abundances and fly fitness traits, including development, reproduction, and lifespan. The fly gut promoted bacterial diversity, which, in turn, accelerated development, reproduction, and aging: Flies that reproduced more died sooner. From these measurements, we calculated the impact of bacterial interactions on fly fitness by adapting the mathematics of genetic epistasis to the microbiome. Development and fecundity converged with higher diversity, suggesting minimal dependence on interactions. However, host lifespan and microbiome abundances were highly dependent on interactions between bacterial species. Higher-order interactions (involving three, four, and five species) occurred in 13–44% of possible cases depending on the trait, with the same interactions affecting multiple traits, a reflection of the life history tradeoff. Overall, we found these interactions were frequently context-dependent and often had the same magnitude as individual species themselves, indicating that the interactions can be as important as the individual species in gut microbiomes.