Theories assuming that representations in working memory decay unless maintained by rehearsal must predict that in any condition where rehearsal does not fully counteract decay, memory declines with a longer retention interval. Two experiments served to test this prediction in a complex-span paradigm in which encoding of letters for later recall alternated with series of spatial distractor operations. The opportunity for rehearsal was varied through cognitive load, the proportion of available time per distractor operation that was actually needed for that operation. The time needed for each operation within a series was measured independently. Retention interval was varied by increasing the number of operations at constant cognitive load. Memory declined with higher cognitive load, but was unchanged (Experiment 1) or improved (Experiment 2) with more distractor operations. Decay theories can explain the effect of cognitive load by assuming that at high load rehearsal fails to fully compensate decay, but then must predict a negative effect of the number of operations at higher cognitive load, contrary to the data. Simulations with an interference-based computational model of working memory, SOB-CS, show that the model explains the experimental findings.