In this study, we used a modified version of the Tower of London (TOL) planning task, in conjunction with positron emission tomography, to examine the neural substrates mediating cognitive skill learning. Twelve healthy, right-handed participants solved a total of 90 different TOL problems. They were scanned on four occasions during the fast learning stage as well as in a condition designed to control for internally guided movements. Practice of the TOL task resulted in a significant decrease in planning, execution, and total time taken to solve the problems. Consistent with the results of previous studies, early performance of the TOL task was associated with increased blood flow activity in the dorsolateral prefrontal, orbitofrontal, and parietal cortices on the left, as well as in the caudate nucleus, cerebellum, and premotor cortex, bilaterally. Interestingly, however, activity in the left caudate nucleus was maintained from the beginning to the end of the learning process, suggesting that this structure plays a role in this type of cognitive skill learning. In addition, correlational analyses revealed that improved performance on the TOL task was associated with a significant decrease of activity in the medial orbitofrontal and frontopolar cortices over the course of learning, areas thought to be involved in decision making, guessing, and monitoring of feedback information. In sum, the results lend further support to the idea that the learning of cognitive skills requiring planning and working memory capacities is mediated through a fronto-striatal network.