Background: Gait impairment is a major motor symptom in Parkinson's disease (PD), and treadmill training is an effective non-pharmacological treatment option. Research question: In this study, the time course, sustainability and transferability of gait adaptations to treadmill training with and without additional postural perturbations were investigated. Methods: 38 PD patients (Hoehn & Yahr 1–3.5) were randomly allocated to eight weeks of treadmill training, performed twice-weekly for 40 min either with (perturbation treadmill training [PTT], n = 18) or without (conventional treadmill training [CTT], n = 20) additional perturbations to the treadmill surface. Spatiotemporal gait parameters were assessed during treadmill walking on a weekly basis (T0–T8), and after three months follow-up (T9). Additional overground gait analyses were performed at T0 and T8 to investigate transfer effects. Results: Treadmill gait variability reduced linearly over the course of 8 weeks in both groups (p <.001; Cohen's d (range): −0.53 to −0.84). Only the PTT group significantly improved in other gait parameters (stride length/time, stance-/swing time), with stride time showing a significant between-group interaction effect (Cohen's d = 0.33; p =.05). Additional between-group interactions indicated more sustained improvements in stance (Cohen's d = 0.85; p =.02) and swing time variability in the PTT group (Cohen's d = 0.82; p =.03) at T9. Overground gait improvements at T8 existed only in stance (d = -0.73; p =.04) and swing time (d = 0.73; p =.04). Discussion: Treadmill stride-to-stride variability reduced substantially and linearly, but transfer to overground walking was limited. Adding postural perturbations tended to increase efficacy and sustainability of several gait parameters. However, since between-group effects were small, more work is necessary to support these findings.