Previous research has shown that performance on problem solving improves over a period of sleep compared to wakefulness. However, these studies have not determined whether sleep is beneficial for problem solving or whether sleep merely mitigates against interference due to an interruption to solution attempts. Sleep-dependent improvements have been described in terms of spreading-activation, which raises the prediction that an effect of sleep should be greater for problems requiring a broader solution search. We presented participants with a set of remote associates tasks that varied in difficulty as a function of the strength of the stimuli-answer associations. After a period of sleep, wake, or no-delay, participants reattempted previously unsolved problems. The sleep group solved more difficult problems than the other groups, but no difference was found for easy problems. We conclude that sleep facilitates problem solving, most likely via spreading activation, but this has its primary effect for harder problems