The primary purpose of this study was to propose and test a mediation model of changes in physical self-efficacy, physical self-perceptions, and affect as mediators by which a single bout of exercise improves state body image. A secondary purpose was to identify how long improvements in state body image are sustained post-exercise. Sixty university-aged women (19.57 ± 1.37 y) with pre-existing body image concerns, and who exercised regularly, were randomized to perform 30 min of moderate-to-vigorous intensity exercise or quiet reading. State body image, physical self-efficacy, physical self-perceptions and affect were assessed. Mediational analyses revealed self-perceptions of body fatness (95% CI [0.03, 0.44], κ2 = 0.13, abps = 0.20) and strength (95% CI [0.15, 0.60], κ2 = 0.23, abps = 0.33) mediated improvements in state body image which were sustained at least 20 min post-exercise. These results contribute to the development of a model explaining the effects of exercise on body image and practical recommendations for the use of exercise to improve body image.