Background: Dopa-resistant freezing of gait (FOG) and falls represent the dominant motor disabilities in advanced Parkinson’s disease (PD). Objective: We investigate the effects of deep brain stimulation (DBS) of the mesencephalic locomotor region (MLR), comprised of the pedunculopontine (PPN) and cuneiform (CuN) nuclei, for treating gait and balance disorders, in a randomized double-blind cross-over trial. Methods: Six PD patients with dopa-resistant FOG and/or falls were operated for MLR-DBS. Patients received three DBS conditions, PPN, CuN, or Sham, in a randomized order for 2-months each, followed by an open-label phase. The primary outcome was the change in anteroposterior anticipatory-postural-adjustments (APAs) during gait initiation on a force platform Results: The anteroposterior APAs were not significantly different between the DBS conditions (median displacement [1st–3rd quartile] of 3.07 [3.12–4.62] cm with sham-DBS, 1.95 [2.29–3.85] cm with PPN-DBS and 2.78 [1.66–4.04] cm with CuN-DBS; p = 0.25). Step length and velocity were significantly higher with CuN-DBS vs. both sham-DBS and PPN-DBS. Conversely, step length and velocity were lower with PPN-DBS vs. sham-DBS, with greater double stance and gait initiation durations. One year after surgery, step length was significantly lower with PPN-DBS vs. inclusion. We did not find any significant change in clinical scales between DBS conditions or one year after surgery. Conclusion: Two months of PPN-DBS or CuN-DBS does not effectively improve clinically dopa-resistant gait and balance disorders in PD patients.