Cross-frequency coupling (CFC) binds neuronal oscillations in sleep and wake, but the mnemonic function of these interactions remains unclear. We recorded scalp electroencephalography from 10 human participants while they slept following a declarative word pair learning task or a non-learning control task. In non rapid-eye-movement sleep (NREMS), delta-sigma phase-amplitude coupling (PAC) was marginally increased in central regions after learning, and its learning-related change in frontal regions was strongly predictive of recall performance the next morning. We observed opposite effects for CFC in rapid-eye-movement sleep (REMS). Delta- and theta-gamma PAC were still significantly increased after learning at fronto-central locations, but the frontal increase was negatively correlated with subsequent recall performance. Importantly, characteristics of the coupled oscillations (delta/slow waves and sigma/spindles in NREMS, and delta, theta and gamma in REMS) showed no learning-related effect. Only their synchronization was mnemonically significant. We propose that NREMS and REMS are opponent processes in their effect on declarative memory consolidation. Whereas NREMS integrates new memories to the knowledge network and stabilizes learned associations through temporally ordered thalamo-cortico-hippocampal reactivations, REMS brings out weak links and encodes them through hippocampo-cortical delta- and theta-gamma PAC, thus weakening the accuracy of waking memories. This interplay is analogous to the trade-off between exploration and exploitation in decision-making research and artificial intelligence.