Exercise is an effective strategy for diabetes management but is limited by the phenomenon of exercise resistance (i.e., the lack of or the adverse response to exercise on metabolic health). Here, in 39 medication-naive men with prediabetes, we found that exercise-induced alterations in the gut microbiota correlated closely with improvements in glucose homeostasis and insulin sensitivity (clinicaltrials.gov entry NCT03240978). The microbiome of responders exhibited an enhanced capacity for biosynthesis of short-chain fatty acids and catabolism of branched-chain amino acids, whereas those of non-responders were characterized by increased production of metabolically detrimental compounds. Fecal microbial transplantation from responders, but not non-responders, mimicked the effects of exercise on alleviation of insulin resistance in obese mice. Furthermore, a machine-learning algorithm integrating baseline microbial signatures accurately predicted personalized glycemic response to exercise in an additional 30 subjects. These findings raise the possibility of maximizing the benefits of exercise by targeting the gut microbiota.