The microbial community in the gut is influenced by environmental factors, especially diet, which can moderate host behaviour through the microbiome-gut-brain axis. However, the ecological relevance of microbiome-mediated behavioural plasticity in wild animals is unknown. We presented wild-caught great tits (Parus major) with a problem-solving task and showed that performance was weakly associated with variation in the gut microbiome. We then manipulated the gut microbiome by feeding birds one of two diets that differed in their relative levels of fat, protein and fibre content: an insect diet (low content), or a seed diet (high content). Microbial communities were less diverse among individuals given the insect compared to those on the seed diet. Individuals were less likely to problem-solve after being given the insect diet, and the same microbiota metrics that were altered as a consequence of diet were also those that correlated with variation in problem solving performance. Although the effect on problem-solving behaviour could have been caused by motivational or nutritional differences between our treatments, our results nevertheless raise the possibility that dietary induced changes in the gut microbiota could be an important mechanism underlying individual behavioural plasticity in wild populations.