The possibility to learn during sleep intrigued humanity for over a century. However, scientific efforts to teach humans novel verbal information during sleep have been largely unsuccessful. Recently, we demonstrated that sleeping humans can learn entirely new non-verbal information and that this information can modulate behavior during wakefulness in a sleep stage dependent manner. Specifically, new associations learned during non-rapid-eye-movement sleep (NREM) had larger and longer lasting influence on behavior than associations learned during rapid–eye-movement (REM) sleep. Moreover, associative learning in sleep modulated learning-related slow waves in NREM sleep, and this modulation was directly linked to the associations retrieval. Altogether, these findings suggest that the modulation of slow waves occurring during the process of learning in sleep may determine the fate of the newly acquired memories.