REM-sleep-behavior-disorder (RBD) is characterized by the absence of muscle-atonia during REM-sleep. RBD is strongly associated with presymptomatic-manifestations of neurodegenerative-synucleinopathies. Thus, it allows the investigation of early/premanifest neurodegenerative-stages when treatment can be most effective in delaying the development of full-blown-disease. Changes in brainstem-nuclei-connectivity are expected in RBD/premanifest-synucleinopathy based on animal- and ex-vivo-human-studies. Yet, their investigation in living-humans is understudied. Through high-spatial-resolution 7Tesla-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, with the striatum and cerebellum in line with the pathophysiology of RBD in animal-models.