Gait dysfunction in Parkinson’s disease (PD) does not always respond to bilateral subthalamic nucleus deep brain stimulation (STN-DBS). Since right hemisphere motor networks may be dominant for gait control, identical stimulation of asymmetric circuits could account for gait dysfunction. We compared the effects of bilateral and unilateral STN-DBS on gait kinematics in PD patients who developed gait impairment after STN-DBS. Twenty-two PD patients with >50 % improvement in motor scores, but dopamine-resistant gait dysfunction 6–12 months after bilateral STN-DBS were blindly tested off dopaminergic effects in four randomly assigned DBS conditions: bilateral, right-sided, left-sided and off stimulation. Motor scores (MDS-UPDRS III), gait scores (MDS-UPRDS 2.11–2.13 + 3.9–3.13), turning time (seconds), stride length (meters) and velocity (meters/second) were measured 1 h after DBS changes. Motor and gait scores significantly improved with bilateral versus unilateral STN-DBS. Stride length and velocity (0.95 ± 0.06, 0.84 ± 0.07) significantly improved with bilateral (1.09 ± 0.04, 0.95 ± 0.05), right-sided (1.06 ± 0.04, 0.92 ± 0.05) and left-sided stimulation (1.01 ± 0.05, 0.90 ± 0.05) (p < 0.05). Stride length significantly improved with right-sided versus left-sided (0.05 ± 0.02) and bilateral versus left-sided stimulation (0.07 ± 0.02) (p < 0.05). Turning time (4.89 ± 0.6) tended to improve with bilateral (4.13 ± 0.5) (p = 0.15) and right-sided (4.27 ± 0.6) (p = 0.2) more than with left STN-DBS (4.69 ± 0.5) (p = 0.5). Bilateral STN-DBS yields greater improvement in motor and gait scores in PD patients. Yet, unilateral stimulation has similar effects on gait kinematics. Particularly, right-sided stimulation might produce slightly greater improvements. Although the clinical relevance of differential programming of right versus left-sided STN-DBS is unclear, this approach could be considered in the management of treatment-resistant gait dysfunction in PD.