The aim was to compare the short and long-term effects of subthalamic nucleus (STN) deep brain stimulation (DBS) on gait dysfunction and other cardinal symptoms of Parkinson's disease (PD). Two groups of patients were studied. The first group (short-term DBS, n = 8) included patients recently implanted with STN DBS (mean time since DBS 15.8 months, mean age 58.8 years, PD duration 13 years); the second group (long-term DBS, n = 10) included patients with at least 5 years of DBS therapy (mean time since DBS 67.6 months, mean age 61.7 years, PD duration 17.1 years). Both groups were examined using the Unified Parkinson's Disease Rating Scale (UPDRS) and Gait and Balance scale (GABS) during four stimulation/medication states (ON/OFF; OFF/OFF; OFF/ON; ON/ON). Data were analyzed using repeated measures ANOVA with time since implantation (years) between groups and medication or DBS effect (ON, OFF) within groups. In the short-term DBS group, stimulation improved all UPDRS subscores similar to dopaminergic medications. In particular, average gait improvement was over 40% (p = 0.01), as measured by the UPDRS item 29 and GABS II. In the long-term DBS group, stimulation consistently improved all clinical subscores with the exception of gait and postural instability. In these patients, the effect of levodopa on gait was partially preserved. Short-term improvement of gait abnormalities appears to significantly decline after 5 years of STN DBS in PD patients, while effectiveness for other symptoms remains stable. Progressive non-dopaminergic (non-DBS responsive) mechanisms or deleterious effects of high frequency STN stimulation on gait function may play a role.