What processes are involved in the formation of enduring memory traces? Sleep has been proposed to play a role in memory consolidation and the present study provides evidence to support 2-stage models of sleep and memory including both non-rapid eye movement (NREM) and rapid eye movement (REM) sleep. Previous research has shown REM sleep increases following avoidance learning and memory is impaired if REM deprivation occurs during these post-training periods indicating that REM sleep may have a role in memory consolidation processes. These discrete post-training periods have been termed REM sleep windows (RSWs). It is not known whether the electroencephalogram has unique characteristics during the RSW. Further investigation of the RSW was one of the primary goals of this study. We investigated the epidural-recorded electrophysiological learning-related changes following avoidance training in rats. Theta power increased in the learning group during the RSW, suggesting that theta is involved in memory consolidation during this period. Sleep spindles subsequently increased in slow wave sleep (SWS). The results suggest that both NREM and REM sleep are involved in sleep-dependent memory consolidation, and provide support for existing 2-stage models. Perhaps first theta increases to organize and consolidate material via hippocampal-neocortical dialogue, followed by subsequent refinement in the cortex by spindles during SWS.