Improvement after practicing visual texture discrimination does not occur until several hours after practice has ended. We show that this improvement strongly depends on sleep. To specify the process responsible for sleep-related improvement, we compared the effects of 'early' and 'late' sleep, dominated respectively by slow-wave and rapid eye movement (REM) sleep. Discrimination skills significantly improved over early sleep, improved even more over a whole night's sleep, but did not improve after late sleep alone. These findings suggest that procedural memory formation is prompted by slow-wave sleep-related processes. Late REM sleep may promote memory formation at a second stage, only after periods of early sleep have occurred.