Exercise seems to enhance the beneficial effect of bariatric (Roux-en-Y gastric bypass [RYGB]) surgery on insulin resistance. We hypothesized that skeletal muscle extracellular matrix (ECM) remodeling may underlie these benefits. Women were randomized to either a combined aerobic and resistance exercise training program following RYGB (RYGB + ET) or standard of care (RYGB). Insulin sensitivity was assessed by oral glucose tolerance test. Muscle biopsy specimens were obtained at baseline and 3 and 9 months after surgery and subjected to comprehensive phenotyping, transcriptome profiling, molecular pathway identification, and validation in vitro. Exercise training improved insulin sensitivity beyond surgery alone (e.g., Matsuda index: RYGB 123% vs. RYGB + ET 325%; P ≤ 0.0001). ECM remodeling was reduced by surgery alone, with an additive benefit of surgery and exercise training (e.g., collagen I: RYGB −41% vs. RYGB + ET −76%; P ≤ 0.0001). Exercise and RYGB had an additive effect on enhancing insulin sensitivity, but surgery alone did not resolve insulin resistance and ECM remodeling. We identified candidates modulated by exercise training that may become therapeutic targets for treating insulin resistance, in particular, the transforming growth factor-β1/SMAD 2/3 pathway and its antagonist follistatin. Exercise-induced increases in insulin sensitivity after bariatric surgery are at least partially mediated by muscle ECM remodeling.