Animals bear communities of gut microorganisms with substantial effects on animal nutrition, but the host genetic basis of these effects is unknown. Here we use Drosophila to demonstrate substantial among-genotype variation in the effects of eliminating the gut microbiota on five host nutritional indices (weight, protein, lipid, glucose and glycogen contents); this includes variation in both the magnitude and direction of microbiota-dependent effects. Genome-wide association studies to identify the genetic basis of the microbiota-dependent variation reveal polymorphisms in largely non-overlapping sets of genes associated with variation in the nutritional traits, including strong representation of conserved genes functioning in signalling. Key genes identified by the GWA study are validated by loss-of-function mutations that altered microbiota-dependent nutritional effects. We conclude that the microbiota interacts with the animal at multiple points in the signalling and regulatory networks that determine animal nutrition. These interactions with the microbiota are probably conserved across animals, including humans.