Previous cross-sectional studies on bodyweight related alterations in brain structure revealed profound changes in the gray matter (GM) and white matter (WM) that resemble findings obtained from individuals with advancing age. This suggests that obesity may lead to structural brain changes that are comparable with brain aging. Here, we asked whether weight-loss-dependent improved metabolic and neurotrophic functioning parallels the reversal of obesity-related alterations in brain structure. To this end we applied magnetic resonance imaging (MRI) together with voxel-based morphometry and diffusion-tensor imaging in overweight to obese individuals who participated in a fitness course with intensive physical training twice a week over a period of 3 months. After the fitness course, participants presented, with inter-individual heterogeneity, a reduced body mass index (BMI), reduced serum leptin concentrations, elevated high-density lipoprotein-cholesterol (HDL-C), and alterations of serum brain-derived neurotrophic factor (BDNF) concentrations suggesting changes of metabolic and neurotrophic function. Exercise-dependent changes in BMI and serum concentration of BDNF, leptin, and HDL-C were related to an increase in GM density in the left hippocampus, the insular cortex, and the left cerebellar lobule. We also observed exercise-dependent changes of diffusivity parameters in surrounding WM structures as well as in the corpus callosum. These findings suggest that weight-loss due to physical exercise in overweight to obese participants induces profound structural brain plasticity, not primarily of sensorimotor brain regions involved in physical exercise, but of regions previously reported to be structurally affected by an increased body weight and functionally implemented in gustation and cognitive processing.