Rapid eye movement (REM) sleep behavior disorder is considered the prodromal stage of alpha-synucleinopathies. Its diagnosis requires careful detection of REM sleep and the gold standard manual sleep staging is inconsistent and expensive. This work proposes a new automatic sleep staging model to add robust automation to such applications, using only electroencephalography (EEG) and electrooculography (EOG) recordings. The publicly available ISRUC-Sleep database was used to optimize the design of the proposed model. The model was trained and tested on subgroup-I consisting of 100 subjects with evidence of having different sleep disorders and the polysomnographic data were manually scored by two individual experts. We divided the EOG and EEG recordings in overlapping moving 33-s epochs with step of 3s and for each of them we computed several time and frequency-domain features. The features were used to train a random forest classifier that was able to label each 33-s epoch with the probabilities of being wakefulness, REM and non-REM. The mean of the probability values of ten 33-s epochs were calculated, and the sleep stage with the highest probability was chosen to classify a 30-s epoch and matched with the manual staged hypnogram. The performance of the model was tested using 20-fold cross validation scheme. When the epochs where the scorers agreed were used, the classification achieved an overall accuracy of 92.6% and a Cohen's kappa of 0.856. Future validation on RBD patients is needed, but these performances are promising as first step of development of an automated diagnosis of RBD.