Major depressive disorder (MDD) is a common psychiatric disorder and the leading cause of disability worldwide. However, current methods used to diagnose depression mainly rely on clinical interviews and self-reported scales of depressive symptoms, which lack objectivity and efficiency. To address this challenge, we present a machine learning approach to screen for MDD using electrodermal activity (EDA). Participants included 30 patients with MDD and 37 healthy controls. Their EDA was measured during five experimental phases consisted of baseline, mental arithmetic task, recovery from the stress task, relaxation task, and recovery from the relaxation task, which elicited multiple alterations in autonomic activity. Selected EDA features were extracted from each phase, and differential EDA features between two distinct phases were evaluated. By using these features as input data and performing feature selection with SVM-RFE, 74% accuracy, 74% sensitivity, and 71% specificity could be achieved by our decision tree classifier. The most relevant features selected by SVM-RFE included differential EDA features and features from the stress and relaxation tasks. These findings suggest that automatic detection of depression based on EDA features is feasible and that monitoring changes in physiological signal when a subject is experiencing autonomic arousal and recovery may enhance discrimination power.