REM sleep behavior disorder (RBD) symptoms in Parkinson's disease (PD) suggest both a clinically and pathologically malignant subtype. However, whether RBD symptoms are associated with alterations in the organization of whole-brain intrinsic functional networks in PD, especially at early disease stages, remains unclear. Here we use resting-state functional MRI, coupled with graph-theoretical approaches and network-based statistics analyses, and validated with large-scale network analyses, to characterize functional brain networks and their relationship with clinical measures in early PD patients with probable RBD (PD+pRBD), early PD patients without probable RBD (PD-pRBD) and healthy controls. Thirty-six PD+pRBD, 57 PD-pRBD and 71 healthy controls were included in the final analyses. The PD+pRBD group demonstrated decreased global efficiency (t = -2.036, P = 0.0432) compared to PD-pRBD, and decreased network efficiency, as well as comprehensively disrupted nodal efficiency and whole-brain networks (all eight networks, but especially in the sensorimotor, default mode and visual networks) compared to healthy controls. The PD-pRBD group showed decreased nodal degree in right ventral frontal cortex and more affected edges in the frontoparietal and ventral attention networks compared to healthy controls. Furthermore, the assortativity coefficient was negatively correlated with Montreal cognitive assessment scores in the PD+pRBD group (r = -0.365, P = 0.026, d = 0.154). The observation of altered whole-brain functional networks and its correlation with cognitive function in PD+pRBD suggest reorganization of the intrinsic functional connectivity to maintain the brain function in the early stage of the disease. Future longitudinal studies following these alterations along disease progression are warranted.