The mechanisms underlying working memory training remain unclear, but one possibility is that the typically limited transfer effects of this training reflect adoption of successful task-specific strategies. Our pre-registered randomized controlled trial (N = 116) studied the early effects of externally given vs. internally generated strategies in an updating task (n-back) over a 5-day period with a single 30-minute training session. Three groups were employed: n-back training with strategy instruction (n = 40), n-back training without strategy instruction (n = 37), and passive controls (n = 39). We found that both external and internal strategy use was associated with significantly higher posttest performance on the trained n-back task, and that training with n-back strategy instruction yielded positive transfer on untrained n-back tasks, resembling the transfer pattern typically seen after the ordinary uninstructed 4–6-week working memory training. In the uninstructed participants, the level of detail and type of internally generated n-back strategies at posttest was significantly related to their posttest n-back performance. Our results support the view that adoption of task-specific strategies plays an important role in working memory training outcomes, and that strategy-based effects are apparent right at the start of training.