The objectives of this study are to investigate heart rate variability (HRV) in major depressive disorder patients (MDD) and healthy controls during different sleep stages, and to examine the association of HRV during sleep and depression severity. Polysomnography was recorded from 15 depressive patients with a higher beck depression inventory index (BDI > 25, H-BDI-D), 15 depressive patients with a lower BDI index (BDI ≤ 25, L-BDI-D) and 15 healthy controls. HRV was calculated during the first three rapid eye movements (REM) periods and non-REM stages (i.e. sleep stage 2 and 3) with time domain, power spectral and fractal analysis. As a result, H-BDI-D patients showed the highest short-term fractal alpha-1 exponent during first REM period and healthy controls had the lowest values. Our results suggest an association between the depression severity and the autonomic nerve function, especially during the first REM sleep. The pathophysiological analysis for this property should be conducted in future prospective studies.