Rhythmic auditory cues can immediately improve gait in Parkinson's disease. However, this effect varies considerably across patients. The factors associated with this individual variability are not known to date. Patients' rhythmic abilities and musicality (e.g., perceptual and singing abilities, emotional response to music, and musical training) may foster a positive response to rhythmic cues. To examine this hypothesis, we measured gait at baseline and with rhythmic cues in 39 non-demented patients with Parkinson's disease and 39 matched healthy controls. Cognition, rhythmic abilities and general musicality were assessed. A response to cueing was qualified as positive when the stimulation led to a clinically meaningful increase in gait speed. We observed that patients with positive response to cueing (n = 17) were more musically trained, aligned more often their steps to the rhythmic cues while walking, and showed better music perception as well as poorer cognitive flexibility than patients with non-positive response (n = 22). Gait performance with rhythmic cues worsened in six patients. We concluded that rhythmic and musical skills, which can be modulated by musical training, may increase beneficial effects of rhythmic auditory cueing in Parkinson's disease. Screening patients in terms of musical/rhythmic abilities and musical training may allow teasing apart patients who are likely to benefit from cueing from those who may worsen their performance due to the stimulation.