Creative thought relies on the reorganisation of existing knowledge. Sleep is known to be important for creative thinking, but there is a debate about which sleep stage is most relevant, and why. I will address this issue by proposing that Rapid Eye Movement sleep, or 'REM', and Non-REM sleep facilitate creativity in different ways. Memory replay mechanisms in Non-REM can abstract rules from corpuses of learned information, while replay in REM may promote novel associations. I propose that the iterative interleaving of REM and Non-REM across a night boosts the formation of complex knowledge frameworks, and allows these frameworks to be restructured - thus facilitating creative thought. My talk will discuss experiments exploring these hypotheses, and the mechanisms for these processes.