Sleep has been shown to promote the generation of explicit knowledge as indicated by the gain of insight into previously unrecognized task regularities. Here, we explored whether this generation of explicit knowledge depends on pre-sleep implicit knowledge, and specified the differential roles of slow-wave sleep (SWS) vs. rapid eye movement (REM) sleep in this process. Implicit and explicit knowledge (insight) related to a hidden regularity were assessed in an associative motor-learning task (number reduction task, NRT), which was performed in two sessions (initial practice and retest) separated by 3 h of either early-night sleep, rich in SWS, or of late-night sleep, rich in REM sleep. About half of the participants developed signs of implicit rule knowledge (i.e., speeded reaction times for responses determined by the hidden regularity) at initial practice preceding early or late sleep. Of these, half developed explicit knowledge across early-night sleep, significantly more than across late-night sleep. In contrast, late-night subjects preferentially remained on the level of implicit rule knowledge after sleep. Participants who did not develop implicit knowledge before sleep had comparable rates of transition to implicit or explicit knowledge across early and late sleep. If subjects gained explicit knowledge across sleep, this was associated with lower amounts of REM sleep, specifically in the late-night group. SWS predominant during the early night may restructure implicit memory representations in a way that allows creating an explicit representation afterward, whereas REM sleep in the late night appears to stabilize them in their implicit form.