Physical exercise has been shown to induce structural plasticity in the human brain and to enhance cognitive functions. While previous studies focused on aerobic exercise, suggesting a link between increased cardiorespiratory fitness and exercise-induced neuroplasticity, recent findings have suggested that whole-body exercise with minor metabolic demands elicits beneficial effects on brain structure as well. In the present study, we tested if balance training, challenging the sensory-motor system and vestibular self-motion perception, induces structural plasticity. Thirty-seven healthy adults aged 19–65 years were randomly assigned to either a balance training or a relaxation training group. All participants exercised twice a week for 12 weeks. Assessments before and after the training included a balance test and the acquisition of high-resolution T1-weighted images to analyze morphological brain changes. Only the balance group significantly improved balance performance after training. Cortical thickness was increased in the superior temporal cortex, in visual association cortices, in the posterior cingulate cortex, in the superior frontal sulcus, and in the precentral gyri in the balance group, compared to the relaxation group. Moreover, there was evidence that the balance training resulted in decreased putamen volume. Improved balance performance correlated with the increase of precentral cortical thickness and the decrease in putamen volume. The results suggest that balance training elicits neuroplasticity in brain regions associated with visual and vestibular self-motion perception. As these regions are known for their role in spatial orienting and memory, stimulating visual-vestibular pathways during self-motion might mediate beneficial effects of physical exercise on cognition.