Healthy sleep consists of several stages: deep sleep, light sleep, and rapid eye movement (REM) sleep. Here we show that these sleep stages can be characterized and distinguished by correlations of heart rates separated by n beats. Using the detrended fluctuation analysis (DFA) up to fourth order we find that long-range correlations reminiscent to the wake phase are present only in the REM phase. In the non-REM phases, the heart rates are uncorrelated above the typical breathing cycle time, pointing to a random regulation of the heartbeat during non-REM sleep.