Physical activity may benefit mental health, yet the potentially protective role of elementary school physical education (PE) on childhood mental health is unknown. The aim of the current study was to determine the effect of a specialist-taught PE program on indicators of childhood mental health. In this cluster-randomized controlled trial, participants were initially 821 healthy children (8 years, 406 girls) from 29 schools. Thirteen schools were allocated to the 4-year intervention program of specialist-taught PE, with the remaining schools forming the control group. Mental health indicators of depression, body image, and stress were measured at ages 7, 8, and 12 years. Assessments of covariates included percent body fat (DEXA), physical activity (pedometers), puberty (Tanner stages), and socioeconomic status. After receiving 1 year of specialist-taught PE, children of the intervention group reported a -0.71-unit decrease in body dissatisfaction compared to a 3.01-unit increase in control group children (p = 0.042); and a mean decrease in depressive symptoms (ineffectiveness), which was -0.27 units more than the control group (p = 0.005). Mixed-model analyses investigating longer-term effects revealed that the early positive effect of the intervention on body dissatisfaction and depression was not sustained over time. In fact, there was evidence of an intervention effect of an overall increase in depressive symptoms over the 4 years of the study for girls only. While our specialist-taught PE intervention had a positive influence on girls' body dissatisfaction and boys' depressive symptoms in the first year, this was not sustained over the 4-year duration of the study.