Traumatic brain injury (TBI) causes lifelong cognitive deficits, particularly impairments of executive functioning (EF). Musical training and music-based rehabilitation have been shown to enhance cognitive functioning and neuroplasticity, but the potential rehabilitative effects of music in TBI are still largely unknown. The aim of the present cross-over randomized controlled trial (RCT) was to determine the clinical efficacy of music therapy on cognitive functioning in TBI and to explore its neural basis. Using an AB/BA design, 40 patients with moderate or severe TBI were randomized to receive a 3-month neurological music therapy intervention either during the first (AB, n = 20) or second (BA, n = 20) half of a 6-month follow-up period. Neuropsychological and motor testing and MRI scanning was performed at baseline and at the 3-month and 6-month stage. 39 subjects who participated in baseline measurement were included in an intention-to-treat analysis using multiple imputation. Results showed that general EF (as indicated by the Frontal Assessment Battery) and set shifting improved more in the AB group than in the BA group over the first 3-month period and the effect on general EF was maintained in the 6-month follow-up. Voxel-based morphometry (VBM) analysis of the structural MRI data indicated that grey matter volume (GMV) in the right inferior frontal gyrus (IFG) increased significantly in both groups during the intervention vs. control period, which also correlated with cognitive improvement in set shifting. These findings suggest that neurological music therapy enhances EF and induces fine-grained neuroanatomical changes in prefrontal areas.