Memory consolidation is most commonly described by the standard model, which proposes an initial binding role for the hippocampus which diminishes over time as intracortical connections are strengthened. Recent evidence suggests that slow wave sleep (SWS) plays an essential role in this process. Existing animal and human studies have suggested that memories which fit tightly into an existing knowledge framework or schema might use an alternative consolidation route in which the medial prefrontal cortex takes on the binding role. In this study we sought to investigate the role of sleep in this process using a novel melodic memory task. Participants were asked to remember 32 melodies, half of which conformed to a tonal schema present in all enculturated listeners, and half of which did not fit with this schema. After a 24-h consolidation interval, participants were asked to remember a further 32 melodies, before being given a recognition test in which melodies from both sessions were presented alongside some previously unheard foils. Participants remembered schema-conformant melodies better than non-conformant ones. This was much more strongly the case for consolidated melodies, suggesting that consolidation over a 24-h period preferentially consolidated schema-conformant items. Overnight sleep was monitored between the sessions, and the extent of the consolidation benefit for schema-conformant items was associated with both the amount of REM sleep obtained and EEG theta power in frontal and central regions during REM sleep. Overall our data suggest that REM sleep plays a crucial role in the rapid consolidation of schema-conformant items. This finding is consistent with previous results from animal studies and the SLIMM model of Van Kesteren, Ruiter, Fernández, and Henson (2012), and suggest that REM sleep, rather than SWS, may be involved in an alternative pathway of consolidation for schema-conformant memories.