Background: An important challenge of school-based childhood obesity (OB) intervention programs is understanding the maintenance of the effects after cessation of the intervention to overcome the limitations of follow-up studies. The aim of this study is to verify the sustainability of the benefits achieved at a 4-year follow-up of the post-Educacio en Alimentacio (EDAl) program intervention cessation by assessing the OB-related outcomes and lifestyles of 13-to 15-year-old adolescents. Methods: This paper describes a 4-year follow-up study after the cessation of a school-based randomized controlled intervention in adolescents (n = 349, intervention; n = 154, control) with baseline and 4-year follow-up data from high schools in Reus (intervention group), Salou, Cambrils and Vila-seca (control group). The outcomes are body mass index (BMI), BMI z-score, and OB prevalence according to the World Health Organization and International Obesity Task Force criteria and lifestyle data (obtained from questionnaires). Results: Compared with the control girls, the intervention girls showed reduced BMI z-scores (-0.33 units, p < 0.01) from baseline (2007) to the 4-year follow-up post-intervention (2014). Compared with the control boys, the intervention boys showed reduced OB prevalence (-7.7%; p = 0.02). Compared with the control boys, more boys in the intervention group (19% increase; p = 0.059) showed = 4 h/week after-school physical activity (PA). A decrease in the consumption of dairy products, fruits and fish was observed in both groups. Conclusions: At the 4-year post-intervention follow-up of the EdAl program, compared with the control groups, girls had lower BMI z-scores and boys had lower OB prevalence from the intervention. The encouragement in after-school PA was long-lasting and maintained after the cessation of the intervention, whereas healthy food habits must be further reinforced in adolescents.