Electroencephalography (EEG) can reveal the abnormalities of dopaminergic subcortico-cortical circuits in patients with Parkinson’s disease (PD). However, conventional time-frequency analysis of EEG signals cannot fully reveal the non-linear processes of neural activities and interactions. A novel Holo-Hilbert Spectral Analysis (HHSA) was applied to reveal non-linear features of resting state EEG in 99 PD patients and 59 healthy controls (HCs). PD patients demonstrated a reduction of β bands in frontal and central regions, and reduction of γ bands in central, parietal, and temporal regions. Compared with early-stage PD patients, late-stage PD patients demonstrated reduction of β bands in the posterior central region, and increased θ and δ2 bands in the left parietal region. θ and β bands in all brain regions were positively correlated with Hamilton depression rating scale scores. Machine learning algorithms using three prioritized HHSA features demonstrated “Bag” with the best accuracy of 0.90, followed by “LogitBoost” with an accuracy of 0.89. Our findings strengthen the application of HHSA to reveal high-dimensional frequency features in EEG signals of PD patients. The EEG characteristics extracted by HHSA are important markers for the identification of depression severity and diagnosis of PD.