An experiment (N = 153) with a computerized version of the Tower of Hanoi (ToH) investigated the effect of repeated practice on problem solving in combination with a self-explanation technique. Within one session, participants solved three blocks of three ToH problems each, the problems being flat-to-flat or tower-to-flat variations of equal average difficulty per block. Depending on their self-reported prior experience, problem solvers were either classified as ToH novices or ToH experts and randomly assigned to one of three verbalization conditions: (a) silent thinking, (b) thinking aloud without specific instruction, (c) self-explanation, i.e., thinking aloud while explaining and justifying each solution step. The expectation that self-explanation promotes efficient problem solving was not supported by a 3 (block) × 2 (expertise) × 3 (verbalization condition) mixed ANOVA with the number of ToH moves above the optimal solution as a dependent variable. Both novices and experts improved over time, especially from the first to the second block. Paralleling this effect, the average duration per solution step decreased, suggesting immediate strategy learning. In the third block the solution performance tended to become worse again, especially for the novices, who became faster but less accurate, and especially under the self-explanation condition. The results are discussed with respect to disadvantages through cognitive (over)load and advantages of non-verbalizable visually based pattern strategies and procedural learning. Follow-up research should investigate this by coding the quality and solution systematics in think-aloud protocols.