REM-sleep-behavior-disorder (RBD) is a sleep disorder characterized by the absence of muscular atonia during REM sleep. RBD patients have a high risk of developing Parkinson’s disease (PD) within 10 years from RBD diagnosis. Thus, RBD allows the investigation of early/prodromal neurodegenerative-stages. Changes in brainstem-nuclei-connectivity are expected in RBD/prodromal-PD based on animal and ex-vivo human-studies. Yet, their investigation in living-humans is understudied. Through high-spatial-resolution 7 Tesla HARDI MRI and a recently-developed probabilistic-brainstem-nuclei-atlas, we built a brainstem-based structural-connectome in living RBD-patients and age-matched controls. Interestingly, in RBD-patients we detected structural-connectivity-changes within the brainstem in line with the pathophysiology of RBD in animal-models.