A widespread brain disorder of present days is depression which influences 264 million of the world's population. Depression may cause diverse undesirable consequences, including poor physical health, suicide, and self-harm if left untreated. Depression may have adverse effects on the personal, social, and professional lives of individuals. Both neurologists and researchers are trying to detect depression by challenging brain signals of Electroencephalogram (EEG) with chaotic and non-stationary characteristics. It is essential to detect early-stage depression to help patients obtain the best treatment promptly to prevent harmful consequences. In this paper, we proposed a new method based on centered correntropy (CC) and empirical wavelet transform (EWT) for the classification of normal and depressed EEG signals. The EEG signals are decomposed to rhythms by EWT and then CC of rhythms is computed as the discrimination feature and fed to K-nearest neighbor and support vector machine (SVM) classifiers. The proposed method was evaluated using EEG signals recorded from 22 depression and 22 normal subjects. We achieved 98.76%, 98.47%, and 99.05% average classification accuracy (ACC), sensitivity, and specificity in a 10-fold cross-validation strategy by using an SVM classifier. Such efficient results conclude that the method proposed can be used as a fast and accurate computer-aided detection system for the diagnosis of patients with depression in clinics and hospitals.