Cognitive skill learning postulates strategy generation and implementation when people learn to perform new tasks. Here we followed self-reported strategy use and objective performance in a working memory (WM) updating task to reveal strategy development that should take place when faced with this novel task. In two pre-registered online experiments with healthy adults, we examined short-term strategy acquisition in a ca 20–30-minute adaptive n-back WM task with 15 task blocks by collecting participants' strategy reports after each block. Experiment 1 showed that (a) about half of the participants reported using a strategy already during the very first task block, (b) changes in selected strategy were most common during the initial task blocks, and (c) more elaborated strategy descriptions predicted better task performance. Experiment 2 mostly replicated these findings, and it additionally showed that compared to open-ended questions, the use of repeated list-based strategy queries influenced subsequent strategy use and task performance, and also indicated higher rates of strategy implementation and strategy change during the task. Strategy use was also a significant predictor of n-back performance, albeit some of the variance it explained was shared with verbal productivity that was measured with a picture description task. The present results concur with the cognitive skill learning perspective and highlight the dynamics of carrying out a demanding cognitive task.