Face recognition is a highly specialized capability that has implicit and explicit memory components. Studies show that learning tasks with facial components are dependent on rapid eye movement and non-rapid eye movement sleep features, including rapid eye movement sleep density and fast sleep spindles. This study aimed to investigate the relationship between sleep-dependent consolidation of memory for faces and partial rapid eye movement sleep deprivation, rapid eye movement density, and fast and slow non-rapid eye movement sleep spindles. Fourteen healthy participants spent 1night each in the laboratory. Prior to bed they completed a virtual reality task in which they interacted with computer-generated characters. Half of the participants (REMD group) underwent a partial rapid eye movement sleep deprivation protocol and half (CTL group) had a normal amount of rapid eye movement sleep. Upon awakening, they completed a face recognition task that contained a mixture of previously encountered faces from the task and new faces. Rapid eye movement density and fast and slow sleep spindles were detected using in-house software. The REMD group performed worse than the CTL group on the face recognition task; however, rapid eye movement duration and rapid eye movement density were not related to task performance. Fast and slow sleep spindles showed differential relationships to task performance, with fast spindles being positively and slow spindles negatively correlated with face recognition. The results support the notion that rapid eye movement and non-rapid eye movement sleep characteristics play complementary roles in face memory consolidation. This study also raises the possibility that fast and slow spindles contribute in opposite ways to sleep-dependent memory consolidation.