Background: As an objective method to detect the neural electrical activity of the brain, electroencephalography (EEG) has been successfully applied to detect major depressive disorder (MDD). However, the performance of the detection algorithm is directly affected by the selection of EEG channels and brain regions. Methods: To solve the aforementioned problems, nonlinear feature Lempel–Ziv complexity (LZC) and frequency domain feature power spectral density (PSD) were extracted to analyze the EEG signals. Additionally, effects of different brain regions and region combinations on detecting MDD were studied with eyes closed and opened in a resting state. Results: The mean LZC of patients with MDD was higher than that of the control group, and the mean PSD of patients with MDD was generally lower than that of the control group. The temporal region is the best brain region for MDD detection with a detection accuracy of 87.4%. The best multi brain regions combination had a detection accuracy of 92.4% and was made up of the frontal, temporal, and central brain regions. Conclusions: This paper validates the effectiveness of multiple brain regions in detecting MDD. It provides new ideas for exploring the pathology of MDD and innovative methods of diagnosis and treatment.