We tested the hypothesis that rapid eye movement (REM) sleep is important for complex associative learning by restricting rats from entering REM sleep for 4 h either immediately after training on an eight-box spatial task (0-4 REMr) or 4 h following training (4-8 REMr). Both groups of REM-restricted rats eventually reached the same overall performance level as did nonrestricted controls, but 0-4 REMr animals were delayed in their improvement in the first few days and lagged behind controls in the middle portion of the training period. More importantly, performance gains of 0-4 REMr rats depended more on simple local cues throughout the 15-d study since, unlike control and 4-8 REMr animals, their error rate increased after daily disruption of the relationship between local (intramaze) cues and the food reward. Thus, although overall performance was only subtly and transiently impaired, due to the ability to use alternate, nonspatial behavioral strategies, complex associative (spatial) learning was persistently impaired by restricting REM for a short critical period each day. (Contains 6 figures.)