The Tower of Hanoi is an old, popular, and engaging puzzle. It is an exceptional puzzle too considering how effective it can be in engendering multiple valuable outcomes when used as a tool for learning. One of the fundamental goals of mathematics teacher preparation is to enable the prospective teacher to develop mathematical habits of mind and to be able to view mathematics from an advanced standpoint. Thirty students in a preservice teacher education program explored the puzzle as a part of the algebra unit in their mathematics course. They engaged with the puzzle through pictorial, numerical, symbolic, and graphical representations and made connections among these representations. In the course of the activity, the prospective teachers displayed multiple paths of inquiry, used cooperative problem solving, and developed greatly in their mathematical thinking. This article also describes the pedagogical issues encountered during their exploration and the scaffolding that was provided to support their progress.