Sleep stabilizes newly acquired memories, a process referred to as memory consolidation. According to recent studies, sleep-dependent consolidation processes might be deployed to different extents for different types of memories. In particular, weaker memories might benefit greater from post-learning sleep than stronger memories. However, under standard testing conditions, sleep-dependent consolidation effects for stronger memories might be obscured by ceiling effects. To test this possibility, we devised a new memory paradigm (Memory Arena) in which participants learned temporospatial arrangements of objects. Prior to a delay period spent either awake or asleep, training thresholds were controlled to yield relatively weak or relatively strong memories. After the delay period, retrieval difficulty was controlled via the presence or absence of a retroactive interference task. Under standard testing conditions (no interference), a sleep-dependent consolidation effect was indeed observed for weaker memories only. Critically though, with increased retrieval demands, sleep-dependent consolidation effects were seen for both weaker and stronger memories. These results suggest that all memories are consolidated during sleep, but that memories of different strengths require different testing conditions to unveil their benefit from post-learning sleep.