We investigated the relationship between autonomic nervous system activity during each sleep stage and the severity of depressive symptoms in patients with major depressive disorder (MDD) and healthy control subjects. Thirty patients with MDD and thirty healthy control subjects matched for sex, age, and body mass index completed standard overnight polysomnography. Depression severity was assessed using the Beck Depression Inventory (BDI). Time- and frequency-domain, and fractal HRV parameters were derived from 5-min electrocardiogram segments during light sleep, deep sleep, rapid eye movement (REM) sleep, and the pre- and post-sleep wake periods. Detrended fluctuation analysis (DFA) alpha-1 values during REM sleep were significantly higher in patients with MDD than in control subjects, and a significant correlation existed between DFA alpha-1 and BDI score in all subjects. DFA alpha-1 was the strongest predictor for the BDI score, along with REM density as a covariate. This study found that compared with controls, patients with MDD show reduced complexity in heart rate during REM sleep, which may represent lower cardiovascular adaptability in these patients, and could lead to cardiac disease. Moreover, DFA alpha-1 values measured during REM sleep may be useful as an indicator for the diagnosis and monitoring of depression.