Background: The Towers of London (TOL) and Hanoi (TOH) have been viewed as equivalent measures of planning and/or problem solving, although recent evidence in adults suggests that the underlying measurement characteristics of these two tasks may differ. As tower tasks are one of the few instruments that can be used to assess executive functioning in young children, the cognitive demands for both tasks merit further examination. Methods: The relation among tower tasks and those of short-term memory, inhibition, and shifting ability were examined in a sample of 118 typically developing young children (M age = 4 years, 9 months, SD = 6 months). Half the children completed TOL and half completed TOH, with groups matched with respect to age, sex, and child vocabulary. Results: Whilst performance on a shifting task uniquely predicted TOH performance, none of the executive function measures were related to TOL performance after statistically controlling for the influence of baseline naming speed. For both tower tasks, performance on a shifting task contributed more strongly on complex trials that required more moves in the counter-intuitive direction relative to the end-state goal, whereas inhibition task performance only predicted performance on complex TOL trials. Conclusions: Successful tower task performance may be determined, at least at higher levels of complexity, by mental flexibility in this age range. However, overall the findings suggest that TOL and TOH are not interchangeable tasks even in young children, and more generally, raise methodological issues regarding the complex nature of executive function tasks.