The objective of this study was to analyze the effects of a physical activity program including both aerobic exercise and cognitively engaging physical activities on children’s physical fitness and executive functions. Children from 3 primary schools (aged 8–12 years) were recruited. A quasi-experimental design was used. Children in the intervention group (n = 53; 19 boys, 34 girls) participated in a 22-week physical activity program for 30 min during lunch recess, twice a week. Children in the control group (n = 52; 32 boys, 20 girls) followed their normal lunch routine. Aerobic fitness, speed and agility, and muscle strength were assessed using the Eurofit test battery. Executive functions were assessed using tasks measuring inhibition (Stroop test), working memory (Visual Memory Span test, Digit Span test), cognitive flexibility (Trailmaking test), and planning (Tower of London). Children in the intervention group showed significantly greater improvement than children in the control group on the Stroop test and Digit Span test, reflecting enhanced inhibition and verbal working memory skills, respectively. No differences were found on any of the physical fitness variables. A physical activity program including aerobic exercise and cognitively engaging physical activities can enhance aspects of executive functioning in primary school children.