Previous research indicates that many important changes in executive functions, or higher cognitive capacities, occur between the ages of three and five years. Additionally, a distinction can be made between the cognitive functions associated with two different cortical regions. The functions of the dorsolateral prefrontal cortex (DL-PFC) are assessed using 'cool' tasks that are abstract and decontextualised. In contrast, the functions of the orbitofrontal cortex (OFC) are assessed using 'hot' tasks that require flexible appraisal of the affective significance of stimuli (Zelazo & Müller, 2002). Different clinical populations have been hypothesized to differ in terms of their impairment on tasks associated with each area of functioning. Current research conclusions regarding the primacy of hot versus cool executive function impairments are limited, however, as they have not taken complexity into account. That is, tasks currently used in investigations of hot and cool executive functions might differ in terms of the complexity of the cognitive processes that the tasks require. Therefore, comparisons across tasks may be misleading because these tasks vary in terms of the demands they place on participants as well as their hot versus cool status. While complexity theories have been applied to a number of cool tasks, only one hot task, those measuring theory-of-mind abilities, have been analysed in terms of complexity. One aim of the current research was to modify several tasks presumed to measure OFC performance to include a complexity manipulation. Tasks from three hot domains (conditional discrimination, the Children's Gambling Task, and future-oriented decision-making) were analysed in terms of their relational complexity, that is, the number of related entities or arguments inherent in a task or concept (Halford, 1993). Based on these complexity analyses, binary-relational and ternary-relational items of each of these tasks were developed or existing tasks were selected and/or modified. The binary-relational items were closely matched to the ternary-relational items in terms of stimuli and procedure, however, they were lower in complexity. After pilot testing, the three new measures of hot executive functioning were included in a larger test battery that was administered to a sample of 120 normally developing 3-, 4-, 5- and 6-year-old children. Existing binary- and ternary-relational items assessing theory-of-mind (a hot task) and three cool measures (transitivity, class inclusion and the Dimensional Change Card Sort test) were also included. The inclusion of measures of both hot and cool executive functions, each with complexity manipulated, allowed for the examination of a possible differential age of emergence of executive abilities associated with the DL-PFC versus the OFC. In support of the relational complexity approach, significant complexity effects were found across all seven tasks. Items at a higher level of complexity were experienced as relatively more difficult by children of all ages. Significant effects of age were also observed, with performance across all tasks increasing with age. The age effects were strongest on the ternary-relational items. The pass-fail data indicated that the majority of children in all age groups succeeded on the binary-relational items. However, it was not until a median of five years of age that children were able to process ternary relations. Consequently, the ternary-relational items produce the greatest differences in performance between the four age groups. The overall pattern of the results also suggested that a distinction can be made between the ages of emergence of abilities associated with the OFC versus the DL-PFC. The results of the pass-fail percentages, patterns of age-related change and age effects on domain factor scores all suggested that while hot executive functions may begin to develop around four years of age, similar levels of improvement are not seen in cool executive functions until five years of age. Thus, the ability to succeed on ternary-relational items of hot executive function tasks appeared to emerge slightly earlier than the cool executive function tasks. Complexity appears to be a critical factor underlying children's performance on executive function tasks, and future assessment regarding the development of executive abilities will benefit from keeping this in mind. While some refinement of new task items may be beneficial, the current test battery may have utility in further examinations of the executive profiles underlying clinical groups, such as children with autism and ADHD.