Aerobic exercise training in women typically results in minimal fat loss, with considerable individual variability. We hypothesized that women with higher baseline body fat would lose more body fat in response to exercise training, and that early fat loss would predict final fat loss. 81 sedentary premenopausal women (age: 30.7±7.8 yrs; ht: 164.5±7.4 cm; wt: 68.2±16.4 kg; %Fat: 38.1±8.8) underwent Dual-energy X-ray Absorptiometry before and after 12 weeks of supervised treadmill walking 3 days/wk for 30 min at 70% of VO2peak. Overall, women did not lose body weight or fat mass. However, considerable individual variability was observed for changes in body weight (-11.7 to +4.8 kg) and fat mass (-11.8 to +3.7 kg). Fifty-five women were classified as compensators, and as a group gained fat mass (25.6±11.1 kg to 26.1±11.3 kg; p < 0.001). The strongest correlates of change in body fat at 12 weeks were change in body weight (r = 0.52) and fat mass (r = 0.48) at 4 weeks. Step-wise regression analysis that included change in body weight and body fat at 4 weeks, and submaximal exercise energy expenditure, yielded a prediction model that explained 37% of the variance in fat mass change (R = 0.37, P < 0.001). Change in body weight and fat mass at 4 weeks were moderate predictors of fat loss, and may potentially be useful for identification of individuals who achieve less than expected weight loss or experience unintended fat gain in response to exercise training.