Since the seminal research by Jenkins and Dallenbach in the 1920s, it has been well proven that sleep has a major effect on the memory of pre-sleep material. However, there is still sparse knowledge about exactly which features of sleep have the most impact. Studies which examined separately the role of non-rapid eye movement (NREM) sleep and rapid eye movement (REM) sleep provided largely controversial results and aroused harsh scientific debate, and the investigation of the link of specific sleep patterns to different memory systems (e.g. declarative vs. procedural) did not fully reconcile these inconsistencies. New research perspectives have been proposed in recent years to overcome the limits of the previous 'single state' approach. Psychological, neurophysiological and neuroanatomical data have recently suggested that NREM and REM sleep both play a part in memory consolidation. We here present the hypothesis that NREM and REM are complementary for memory processes during sleep, thanks to their close interaction within the NREM-REM cycle, and discuss experimental data which prove the critical role of the sleep cycle for the morning recall of verbal material.