Objectives: To investigate electroencephalographic (EEG), electrooculographic (EOG) and micro-sleep abnormalities associated with rapid eye movement (REM) sleep behavior disorder (RBD) and REM behavioral events (RBEs) in Parkinson's disease (PD). Methods: We developed an automated system using only EEG and EOG signals. First, automatic macro- (30-s epochs) and micro-sleep (5-s mini-epochs) staging was performed. Features describing micro-sleep structure, EEG spectral content, EEG coherence, EEG complexity, and EOG energy were derived. All features were input to an ensemble of random forests, giving as outputs the probabilities of having RBD or not (P (RBD) and P (nonRBD), respectively). A patient was classified as having RBD if P (RBD)≥P (nonRBD). The system was applied to 107 de novo PD patients: 54 had normal REM sleep (PDnonRBD), 26 had RBD (PD + RBD), and 27 had at least two RBEs without meeting electromyographic RBD cut-off (PD + RBE). Sleep diagnoses were made with video-polysomnography (v-PSG). Results: Considering PDnonRBD and PD + RBD patients only, the system identified RBD with accuracy, sensitivity, and specificity over 80%. Among the features, micro-sleep instability had the highest importance for RBD identification. Considering PD + RBE patients, the ones who developed definite RBD after two years had significantly higher values of P (RBD) at baseline compared to the ones who did not. The former were distinguished from the latter with sensitivity and specificity over 75%. Conclusions: Our method identifies RBD in PD patients using only EEG and EOG signals. Micro-sleep instability could be a biomarker for RBD and for proximity of conversion from RBEs, as prodromal RBD, to definite RBD in PD patients.