Sleep is known to benefit memory consolidation, but little is known about the contribution of sleep stages within the sleep cycle. The sequential hypothesis proposes that memories are first replayed during nonrapid-eye-movement (NREM or N) sleep and then integrated into existing networks during rapid-eye-movement (REM or R) sleep, two successive critical steps for memory consolidation. However, it lacks experimental evidence as N always precedes R sleep in physiological conditions. We tested this sequential hypothesis in patients with central hypersomnolence disorder, including patients with narcolepsy who present the unique, anti-physiological peculiarity of frequently falling asleep in R sleep before entering N sleep. Patients performed a visual perceptual learning task before and after daytime naps stopped after one sleep cycle, starting in N or R sleep and followed by the other stage (i.e. N-R vs. R-N sleep sequence). We compared over-nap changes in performance, reflecting memory consolidation, depending on the sleep sequence during the nap. Thirty-six patients who slept for a total of 67 naps were included in the analysis. Results show that sleep spindles are associated with memory consolidation only when N is followed by R sleep, that is in physiologically ordered N-R naps, thus providing support to the sequential hypothesis in humans. In addition, we found a negative effect of rapid-eye-movements in R sleep on perceptual consolidation, highlighting the complex role of sleep stages in the balance to remember and to forget.