Abstract Background The gut microbiome regulates host energy balance and adiposity-related metabolic consequences, but it remains unknown how the gut microbiome modulates body weight response to physical activity (PA). Methods Nested in the Health Professionals Follow-up Study, a subcohort of 307 healthy men (mean[SD] age, 70[4] years) provided stool and blood samples in 2012–2013. Data from cohort long-term follow-ups and from the accelerometer, doubly labeled water, and plasma biomarker measurements during the time of stool collection were used to assess long-term and short-term associations of PA with adiposity. The gut microbiome was profiled by shotgun metagenomics and metatranscriptomics. A subcohort of 209 healthy women from the Nurses’ Health Study II was used for validation. Results The microbial species Alistipes putredinis was found to modify the association between PA and body weight. Specifically, in individuals with higher abundance of A. putredinis, each 15-MET-hour/week increment in long-term PA was associated with 2.26 kg (95% CI, 1.53–2.98 kg) less weight gain from age 21 to the time of stool collection, whereas those with lower abundance of A. putredinis only had 1.01 kg (95% CI, 0.41–1.61 kg) less weight gain (p interaction = 0.019). Consistent modification associated with A. putredinis was observed for short-term PA in relation to BMI, fat mass%, plasma HbA1c, and 6-month weight change. This modification effect might be partly attributable to four metabolic pathways encoded by A. putredinis, including folate transformation, fatty acid β-oxidation, gluconeogenesis, and stearate biosynthesis. Conclusions A greater abundance of A. putredinis may strengthen the beneficial association of PA with body weight change, suggesting the potential of gut microbial intervention to improve the efficacy of PA in body weight management. Video Abstract