PURPOSE: Fitness, physical activity, body composition, and sleep have all been proposed to explain differences in brain health. We hypothesized that an exercise intervention would result in improved fitness and body composition and would be associated with improved structural brain health. METHODS: In a randomized controlled trial, we studied 485 older adults who engaged in an exercise intervention ( n = 225) or a nonexercise comparison condition ( n = 260). Using magnetic resonance imaging, we estimated the physiological age of the brain (BrainAge) and derived a predicted age difference compared with chronological age (brain-predicted age difference (BrainPAD)). Aerobic capacity, physical activity, sleep, and body composition were assessed and their impact on BrainPAD explored. RESULTS: There were no significant differences between experimental groups for any variable at any time point. The intervention group gained fitness, improved body composition, and increased total sleep time but did not have significant changes in BrainPAD. Analyses of changes in BrainPAD independent of group assignment indicated significant associations with changes in body fat percentage ( r (479) = 0.154, P = 0.001), and visceral adipose tissue (VAT) ( r (478) = 0.141, P = 0.002), but not fitness ( r (406) = -0.075, P = 0.129), sleep ( r (467) range, -0.017 to 0.063; P range, 0.171 to 0.710), or physical activity ( r (471) = -0.035, P = 0.444). With linear regression, changes in body fat percentage and VAT significantly predicted changes in BrainPAD ( ß = 0.948, P = 0.003) with 1-kg change in VAT predicting 0.948 yr of change in BrainPAD. CONCLUSIONS: In cognitively normal older adults, exercise did not appear to impact BrainPAD, although it was effective in improving fitness and body composition. Changes in body composition, but not fitness, physical activity, or sleep impacted BrainPAD. These findings suggest that focus on weight control, particularly reduction of central obesity, could be an interventional target to promote healthier brains.