Background: Movement sonification has been recently introduced into the field of neuromotor rehabilitation alongside Neurologic Music Therapy and music-based interventions. This study introduces the use of musical auditory cues encompassing the melodic-harmonic aspect of music. Methods: Nineteen patients with Parkinson’s disease were randomly assigned to the experimental (n = 10) and control (n = 9) groups and underwent thrice-weekly sessions of the same gait training program, with or without sonification. Functional and motor parameters, as well as fatigue, quality of life, and the impact of intervention on patients’ well-being, were assessed at baseline (PRE), the end of treatment (POST), and at follow-up (FU). Between-group differences were assessed for each outcome measure using linear mixed-effects models. The outcome measure was entered as the dependent variable, group and time as fixed effects, and time by group as the interaction effect. Results: Mini BESTest and Dynamic Gait Index scores significantly improved in the experimental group (p = 0.01 and p = 0.03, respectively) from PRE to FU, demonstrating a significant impact of the sonification treatment on balance. No other significant differences were observed in the outcome measures. Conclusions: Larger sample sizes are needed to confirm the effectiveness of sonification approaches in Parkinson’s disease, as well as in other neurological disorders.