This study tested the association between aerobic fitness and executive function and the impact of enhanced, cognitively challenging physical activity on executive function in overweight and lean children. Seventy children aged 9-10 years were assigned to either a 6-month enhanced physical education programme including cognitively demanding (open skill) activities or curricular physical education only. Pre- and post-intervention tests assessed aerobic capacity (Leger test) and two components of executive function: inhibition and working memory updating (random number generation task). Indices of inhibition and memory updating were compared in higher- and lower-fit children and intervention effects were evaluated as a function of physical activity programme (enhanced vs. curricular) and weight status (lean vs. overweight). Results showed better inhibition in higher- than lower-fit children, extending the existing evidence of the association between aerobic fitness and executive function to new aspects of children's inhibitory ability. Overweight children had more pronounced pre- to post-intervention improvements in inhibition than lean children only if involved in enhanced physical education. Such intervention effects were not mediated by aerobic fitness gains. Therefore, the cognitive and social interaction challenges inherent in open skill tasks, even though embedded in a low-dose physical activity programme, may represent an effective means to promote cognitive efficiency, especially in overweight children.