Freezing of gait is one of the most debilitating symptoms in Parkinson’s disease as it causes falls and reduces mobility and quality of life. The pedunculopontine nucleus is one of the major nuclei of the mesencephalic locomotor region and has neurons related to anticipatory postural adjustments preceding step initiation as well as to the step itself, thus it may be critical for coupling posture and gait to avoid freezing. Because freezing of gait and postural impairments have been related to frontal lesions and frontal dysfunction such as executive function, we hypothesized that freezing is associated with disrupted connectivity between midbrain locomotor regions and medial frontal cortex. We used diffusion tensor imaging to quantify structural connectivity of the pedunculopontine nucleus in patients with Parkinson’s disease with freezing of gait, without freezing, and healthy age-matched controls. We also included behavioural tasks to gauge severity of freezing of gait, quantify gait metrics, and assess executive cognitive functions to determine whether between-group differences in executive dysfunction were related to pedunculopontine nucleus structural network connectivity. Using seed regions from the pedunculopontine nucleus, we were able to delineate white matter connections between the spinal cord, cerebellum, pedunculopontine nucleus, subcortical and frontal/prefrontal cortical regions. The current study is the first to demonstrate differences in structural connectivity of the identified locomotor pathway in patients with freezing of gait. We report reduced connectivity of the pedunculopontine nucleus with the cerebellum, thalamus and multiple regions of the frontal cortex. Moreover, these structural differences were observed solely in the right hemisphere of patients with freezing of gait. Finally, we show that the more left hemisphere-lateralized the pedunculopontine nucleus tract volume, the poorer the performance on cognitive tasks requiring the initiation of appropriate actions and/or the inhibition of inappropriate actions, specifically within patients with freezing. These results support the notion that freezing of gait is strongly related to structural deficits in the right hemisphere’s locomotor network involving prefrontal cortical areas involved in executive inhibition function.