The importance of sleep for memory consolidation has been firmly established over the past decade. Recent work has extended this by suggesting that sleep is also critical for the integration of disparate fragments of information into a unified schema, and for the abstraction of underlying rules. The question of which aspects of sleep play a significant role in integration and abstraction is, however, currently unresolved. Here, we examined the role of sleep in abstraction of the implicit probabilistic structure in sequential stimuli using a statistical learning paradigm, and tested for its role in such abstraction by searching for a predictive relationship between the type of sleep obtained and subsequent performance improvements using polysomnography. In our experiments, participants were exposed to a series of tones in a probabilistically determined sequential structure, and subsequently tested for recognition of novel short sequences adhering to this same statistical pattern in both immediate- and delayed-recall sessions. Participants who consolidated over a night of sleep improved significantly more than those who consolidated over an equivalent period of daytime wakefulness. Similarly, participants who consolidated across a 4-h afternoon delay containing a nap improved significantly more than those who consolidated across an equivalent period without a nap. Importantly, polysomnography revealed a significant correlation between the level of improvement and the amount of slow-wave sleep obtained. We also found evidence of a time-based consolidation process which operates alongside sleep-specific consolidation. These results demonstrate that abstraction of statistical patterns benefits from sleep, and provide the first clear support for the role of slow-wave sleep in this consolidation.