Background. No single intervention restores the coordinated components of gait after stroke. Objective. The authors tested the multimodal Gait Training Protocol, with or without functional electrical stimulation (FES), to improve volitional walking (without FES) in patients with persistent (>6 months) dyscoordinated gait. Methods. A total of 53 subjects were stratified and randomly allocated to either FES with intramuscular (IM) electrodes (FES-IM) or No-FES. Both groups received 1.5-hour training sessions 4 times a week for 12 weeks of coordination exercises, body weight–supported treadmill training (BWSTT), and over-ground walking, provided with FES-IM or No-FES. The primary outcome was the Gait Assessment and Intervention Tool (G.A.I.T.) of coordinated movement components, with secondary measures, including manual muscle testing, isolated leg movements (Fugl-Meyer scale), 6-Minute Walk Test, and Locomotion/Mobility subscale of the Functional Independence Measure (FIM). Results. No baseline differences in subject characteristics and measures were found. The G.A.I.T. showed an additive advantage with FES-IM versus No-FES (parameter statistic 1.10; P = .045, 95% CI = 0.023-2.179) at the end of training. For both FES-IM and No-FES, a within-group, pre/posttreatment gain was present for all measures (P < .05), and a continued benefit from mid- to posttreatment (P < .05) was present. For FES-IM, recovered coordinated gait persisted at 6-month follow-up but not for No-FES. Conclusion. Improved gait coordination and function were produced by the multimodal Gait Training Protocol. FES-IM added significant gains that were maintained for 6 months after the completion of training.