Sleep plays an important role in the consolidation of recent memories. However, the cellular and synaptic mechanisms of consolidation during sleep remain poorly understood. In this study, using a realistic computational model of the thalamocortical network, we tested the role of Non-Rapid Eye Movement (NREM) sleep in memory consolidation. We found that sleep spindles (the hallmark of N2 stage sleep) and slow oscillations (the hallmark of N3 stage sleep) both promote replay of the spike sequences learned in the awake state and replay was localized at the trained network locations. Memory performance improved after a period of NREM sleep but not after the same time period in awake. When multiple memories were trained, the local nature of the spike sequence replay during spindles allowed replay of the distinct memory traces independently, while slow oscillations promoted competition that could prevent replay of the weak memories in a presence of the stronger memory traces. This could lead to extinction of the weak memories unless when sleep spindles (N2 sleep) preceded slow oscillations (N3 sleep), as observed during the natural sleep cycle. Our study presents a mechanistic explanation for the role of sleep rhythms in memory consolidation and proposes a testable hypothesis how the natural structure of sleep stages provides an optimal environment to consolidate memories.