The Tower of London (TOL) task has been widely used in both clinical and research realms. In the current study, 104 healthy participants attempted all possible moderate- to high-difficulty TOL problems in order to determine: (1) optimal measures of problem solving performance, (2) problem characteristics, other than the minimum moves necessary to solve the problem, that determine participants' difficulty in solving problems successfully, quickly, and efficiently, and (3) effects of increased task experience on which problem characteristics determine problem difficulty. A factor analysis of six performance measures found that, regardless of task experience, problem difficulty could be captured well either by a single factor corresponding to general quality of solution or possibly by three subordinate factors corresponding to solution efficiency, solution speed, and initial planning speed. Regression analyses predicting these performance factors revealed that in addition to a problem's minimum moves three problem parameters were critical in determining the problem difficulty: goal position hierarchy, start position hierarchy, and number of solution paths available. The relative contributions of each of the characteristics strongly depended on which performance factor defined performance. We conclude that TOL problem performance is multifaceted, and that classifying problem difficulty using only the minimum moves necessary to solve the problem is inadequate. (Contains 1 figure and 6 tables.)