Objectives: The aim of this randomized controlled trial was to examine the effects of an 8-week program of regular brisk walking, regular brisk walking with abdominal electrical muscle stimulation (EMS), and no exercise on hierarchical self-perceptions, and consider the mediating role of changes in anthropometric measures and body composition. Methods: Thirty-seven sedentary healthy women (mean age=38.1; SD=9.3) provided written informed consent and participated in baseline testing on a range of anthropometric, body composition, and hierarchical self-perception measures. Subsequently participants were randomly assigned to an 8-week program of walking (n = 13), walking+EMS (n = 14), or a control (n = 10) condition. At 8 weeks anthropometric, body composition and self-perception measures were re-assessed. Results: In comparison with the control group, both walking groups had significant reductions in a number of anthropometric measures and improvements in self-perception measures. The improvements on both anthropometric measures and self-perceptions were greater for the walking+EMS condition, which indicated that changes in self-perception might be mediated by body changes. However, an assessment of the mediation effect between changes in anthropometric measures and self-perception changes did not support this finding. Conclusions: An 8-week exercise program results in significant improvements in anthropometric measures and self-perceptions compared with no exercise. Changes in anthropometric measures appear to have limited influence on exercise-induced changes in self-perception and it is suggested that a subjective feeling that one's body is improving may be sufficient to enhance self-perceptions. © 2006 Elsevier Ltd. All rights reserved.