Flexible or 'fluid' cognitive processes are regarded as fundamental to problem solving and creative ability, requiring a specific neurophysiological milieu. REM-sleep dreaming is associated with creative processes and abstract reasoning with increased strength of weak associations in cognitive networks. REM sleep is also mediated by a distinctive neurophysiological profile, different to that of wake and NREM sleep. This study compared the performance of 16 subjects on a test of cognitive flexibility using anagram word puzzles following REM and NREM awakenings across the night, and waking performances during the day. REM awakenings provided a significant 32% advantage in the number of anagrams solved compared with NREM awakenings and was equal to that of wake time trials. Correlations of individual performance profiles suggest that REM sleep may offer a different mode of problem solving compared with wake and NREM. When early and late REM and NREM awakening data were separated, a dissociation was evident, with NREM task performance becoming more REM-like later in the night, while REM performance remained constant. These data suggest that the neurophysiology of REM sleep represents a brain state more amenable to flexible cognitive processing than NREM and different from that in wake, and may offer insights into the neurocognitive properties of REM-sleep dreaming.