Characterized by dream-enactment motor manifestations arising from rapid eye movement (REM) sleep, REM sleep behavior disorder (RBD) is frequently encountered in Parkinson’s disease (PD). Yet the specific neurostructural changes associated with RBD in PD patients remain to be revealed by neuroimaging. Here we identified such neurostructural alterations by comparing large samples of magnetic resonance imaging (MRI) scans in 69 PD patients with probable RBD, 240 patients without RBD and 138 healthy controls, using deformation-based morphometry (p < 0.05 corrected for multiple comparisons). All data were extracted from the Parkinson’s Progression Markers Initiative. PD patients with probable RBD showed smaller volumes than patients without RBD and than healthy controls in the pontomesencephalic tegmentum, medullary reticular formation, hypothalamus, thalamus, putamen, amygdala and anterior cingulate cortex. These results demonstrate that RBD is associated with a prominent loss of volume in the pontomesencephalic tegmentum, where cholinergic, GABAergic and glutamatergic neurons are located and implicated in the promotion of REM sleep and muscle atonia. It is additionally associated with more widespread atrophy in other subcortical and cortical regions whose loss also likely contributes to the altered regulation of sleep-wake states and motor activity underlying RBD in PD patients.