The ability to plan and search ahead is essential for problem solving in most situations in everyday life. To investigate the development of planning and related processes, a sample of four- and five-year-old children was examined in a variant of the Tower of London, a frequently used neuropsychological assessment tool of planning abilities. The applied problems either required searching ahead for optimal solution or were solvable by pure step-by-step forward processing. Furthermore, the ambiguity of subgoal ordering was varied. Results revealed an age-related effect of search depth: the four-year olds' planning accuracy was particularly decreased in problems demanding search ahead, while five-year olds mastered both problem types equally well. Interestingly, this interaction between age and search depth could not be accounted for by measures of working memory and inhibition. Differential effects of age were also found for subgoal ordering with respect to initial planning and movement execution times. In sum, planning abilities showed considerable development during late kindergarten age that appeared to be specifically associated with the integration and back-validation of the anticipated consequences of internally modeled actions. The present study demonstrates that a careful consideration of problem structure may greatly enhance the insights gained from the application of a routinely used assessment tool, the Tower of London. This may be especially advantageous when addressing specific subpopulations such as children or clinical samples.