Sleep-associated consolidation plays an important role in language learning (Dumay & Gaskell, 2007; Gomez et al., 2006). Here we test the hypothesis that greater levels of arbitrariness in the material to be learned are associated with an increased involvement of sleep (Eichenbaum et al., 1999). Two participant groups were trained to equivalent levels on novel words incorporating regularities mirroring a grammatical gender system. After training, participants had a 90-min break filled with either a polysomnographically recorded nap or an awake control task. Subsequently, the nap group outperformed the wake group in recognition and recall of the trained vocabulary items. Both groups showed evidence of generalization of the systematic aspects of the grammar to untrained items, but the nap group outperformed the awake on the grammar test on the trained items. The findings are discussed in the context of the Complementary Learning Systems approach (Kumaran & McClelland, 2012; McClelland etal. 1995).