Physical activity is essential in weight management, improves overall health, and mitigates obesity-related risk markers. Besides inducing changes in systemic metabolism, habitual exercise may improve gut's microbial diversity and increase the abundance of beneficial taxa in a correlated fashion. Since there is a lack of integrative omics studies on exercise and overweight populations, we studied the metabolomes and gut microbiota associated with programmed exercise in obese individuals. We measured the serum and fecal metabolites of 17 adult women with overweight during a 6-week endurance exercise program. Further, we integrated the exercise-responsive metabolites with variations in the gut microbiome and cardiorespiratory parameters. We found clear correlation with several serum and fecal metabolites, and metabolic pathways, during the exercise period in comparison to the control period, indicating increased lipid oxidation and oxidative stress. Especially, exercise caused co-occurring increase in levels of serum lyso-phosphatidylcholine moieties and fecal glycerophosphocholine. This signature was associated with several microbial metagenome pathways and the abundance of Akkermansia. The study demonstrates that, in the absence of body composition changes, aerobic exercise can induce metabolic shifts that provide substrates for beneficial gut microbiota in overweight individuals.