Exercise exerts a wide range of beneficial effects for healthy physiology, and the sedentary lifestyle of modern human societies is associated with several major diseases1-5. However, the mechanisms regulating an individual’s motivation to engage in physical activity remain incompletely understood. An important factor stimulating the engagement in both competitive and recreational exercise is the motivating pleasure derived from prolonged physical activity, colloquially referred to as the “runner’s high”, which is triggered by exercise-induced release of neurotransmitters. Here, we report on the discovery of a connection between the intestinal microbiome, endocannabinoid metabolites, afferent sensory neurons, and the ventral striatum that enhances exercise performance by augmenting physical activity-induced dopamine signaling. Microbiome-dependent production of fatty acid amides in the gut stimulates the activity of Trpv1-expressing neurons and thereby elevates dopamine levels in the nucleus accumbens during physical activity. Consequently, microbiome depletion, ablation of sensory neurons, endocannabinoid receptor inhibition, or dopamine blockade abrogate exercise performance. These findings indicate that the rewarding properties of exercise are influenced by gut-derived interoceptive circuits and provide a microbiome-dependent explanation for inter-individual variability in exercise performance. Our study also suggests that interoceptomimetic molecules that stimulate the transmission of gut-derived signals to the brain may enhance the motivation for exercise.