This RCT investigated the effect on children of integrating physical activity (PA) into math lessons. The primary outcome was math achievement and the secondary outcomes were executive functions, fitness and body mass index. Twelve Danish schools were randomized to either an intervention group or a control group. A total of 505 children with mean age 7.2 ± 0.3 years were enrolled in the study. Change in math achievement was measured by a 45-minute standardized math test, change in executive function by a modified Eriksen flanker task, aerobic fitness by the Andersen intermittent shuttle-run test, and body mass index by standard procedures. PA during the math lessons and total PA (including time spent outside school) were assessed using accelerometry (ActiGraph, GT3X and GT3X+). Children in the intervention group improved their math score by 1.2 (95% CI 0.3; 2.1) more than the control group (p = 0.011) and had a tendency towards a higher change in physical activity level during math lessons of 120,4 counts/min (95% CI -9.0;249.8.2, p = 0.067). However, the intervention did not affect executive functions, fitness or body mass index. Participation in a 9-month PA intervention (from 2012–2013) improved math achievement among elementary school children. If replicated, these findings would suggest that implementation of physical activity in school settings could lead to higher academic achievement.