Vertebrates harbour diverse communities of symbiotic gut microbes. Host diet is known to alter microbiota composition, implying that dietary treatments might alleviate diseases arising from altered microbial composition (‘dysbiosis’). However, it remains unclear whether diet effects are general or depend on host genotype. Here we show that gut microbiota composition depends on interactions between host diet and sex within populations of wild and laboratory fish, laboratory mice and humans.