BACKGROUND: The current method to evaluate major depressive disorder (MDD) relies on subjective clinical interviews and self-questionnaires. OBJECTIVE: Autonomic imbalance in MDD patients is characterized using entropy measures of heart rate variability (HRV). A machine learning approach for screening depression based on the entropy is demonstrated. METHODS: The participants experience five experimental phases: baseline (BASE), stress task (MAT), stress task recovery (REC1), relaxation task (RLX), and relaxation task recovery (REC2). The four entropy indices, approximate entropy, sample entropy, fuzzy entropy, and Shannon entropy, are extracted for each phase, and a total of 20 features are used. A support vector machine classifier and recursive feature elimination are employed for classification. RESULTS: The entropy features are lower in the MDD group; however, the disease does not have a significant effect. Experimental tasks significantly affect the features. The entropy did not recover during REC1. The differences in the entropy features between the two groups increased after MAT and showed the largest gap in REC2. We achieved 70% accuracy, 64% sensitivity, and 76% specificity with three optimal features during RLX and REC2. CONCLUSION: Monitoring of HRV complexity changes when a subject experiences autonomic arousal and recovery can potentially facilitate objective depression recognition.