Efficient execution of strategies is crucial to memory performance and to age-related differences in this performance. Relative strategy complexity influences memory performance and aging effects on memory. Here, we aimed to further our understanding of the effects of relative strategy complexity by looking at the role of cognitive control functions and the time-course of the effects of relative strategy complexity. Thus, we manipulated inter-stimulus intervals (ISI) and assessed executive functions. Results showed that (a) performance as a function of the relative strategy difficulty of the current and previous trial was modulated by ISI, (b) these effects were modulated by inhibition capacities, and (c) significant age differences were found in the way ISI modulates relative strategy difficulty. These findings have important implications for understanding the relationships between aging, executive control, and strategy execution in episodic memory.