People with Parkinson's disease (PD) have difficulty learning new motor skills. Evidence suggests external stimuli (cues) may enhance learning; however, this may be specific to cued rather than non-cued performance. We aimed to test effects of cued training on motor learning in PD. We defined motor learning as acquisition (single task), automaticity (dual task) and retention of single- and dual-task performance (follow-up). 153 subjects with PD received 3 weeks cued gait training as part of a randomised trial (the RESCUE trial). We measured changes in cued gait performance with three external rhythmical cues (ERC) (auditory, visual and somatosensory) during single and dual tasks after training and 6 weeks follow-up. Gait was tested without cues to compare specificity of learning (transfer). Subjects were ‘on’ medication and were cued at preferred step frequency during assessment. Accelerometers recorded gait and walking speed, step length and step frequency were determined from raw data. Data were analysed with SAS using linear regression models. Walking speed and step length significantly increased with all cues after training during both single- and dual-task gait and these effects were retained. Training effects were not specific to cued gait and were observed in dual-task step length, and walking speed however was more limited in single-task non-cued gait. These results support the use of ERC to enhance motor learning in PD as defined by increased acquisition, automaticity and retention. They also highlight the potential for sustained improvement in walking and complex task performance.