It has been debated whether different stages in the human sleep cycle preferentially mediate the consolidation of explicit and implicit memories, or whether all of the stages in succession are necessary for optimal consolidation. We investigated whether the selective deprivation of slow wave sleep (SWS) or rapid eye movement (REM) sleep over an entire night would have a specific effect on consolidation in explicit and implicit memory tasks. Participants had one control night of undisturbed sleep and two experimental nights, during which either SWS or REM sleep was selectively deprived across the entire night. Polysomnography recordings quantified precisely the amount of SWS and REM sleep that occurred during each of the sleep conditions, and spindle counts were recorded. SWS deprivation disrupted the consolidation of explicit memories for visuospatial information, and both SWS and REM sleep deprivation adversely affected explicit verbal recall. Spindle counts did not correlate significantly with memory performance. These findings demonstrate the importance of measuring the sleep cycles throughout the entire night, and the contribution of both SWS and REM sleep to memory consolidation.