Problem-solving theories have not examined how solvers navigate their knowledge to interpret problem situations or to plan strategies toward goals. In this article, the author argues that success in problem solving depends on the solver's ability to construct goal-derived categories, namely categories that are formed ad hoc to serve goals during the instantiation of problem frames. Experiment 1 (N = 140) showed improved problem-solving performance after training to construct goal-derived categories. Experiment 2 (N = 80) demonstrated that effects of training in category construction can be obtained without participants being explicitly informed regarding the relevance of training to problem solving. These studies suggest that problem solving is a dynamic expression of goal-directed cognition and provide evidence for the involvement of categorization in problem-solving processes.