Introduction: Nutrition education during adolescence has proven effective in increasing knowledge, attitudes, and practices in the diet. The Mediterranean diet has proven health benefits and is proposed as a model of a sustainable diet that is beneficial for health and the environment. Its promotion with the educational program can have a significant effect on improvements in nutrition knowledge, diet quality, and nutritive status of adolescents for their healthy adulthood. Objective: This study aimed to investigate the effect of the educational program on the nutrition knowledge, diet quality, lifestyle, and nutritional status of school children from the littoral part of Croatia. Methods: An education-based intervention study was carried out on 2,709 schoolchildren aged 10–12 years (educated/control group: 2617/92). The questionnaire about sociodemographic, anthropometric, dietary, physical activity, screen time, sleep habits, and nutrition knowledge was assessed at the baseline and after a 6- to 9-month follow-up for the medium-term effect of education. Nutrition knowledge was provided after 3 weeks for the short-term education effect assessment. Results: Educated schoolchildren achieved a significant increase in nutrition knowledge (+75.5%), expressed as a short-term effect of the education and maintained at the 6- to 9-month follow-up (+66.8%, p < 0.001). Follow-up of children significantly improved their nutritional status (underweight −56.6%, normal weight 24.8%, overweight −22.1%, and obesity −57.5%) and physical activity engagement (+13.2%). The proportion of children with a diet highly adhering to the Mediterranean diet significantly doubled (+105.0). Those children with the highest nutrition knowledge at the follow-up significantly improved their nutritional status (+218.9%), participated in organized sports (+204.7%), and had a diet that highly adhered to the MD (+291.8%). Conclusion: A significantly good medium-term effect of education-based nutrition and lifestyle intervention program on nutrition knowledge, diet quality, lifestyle, and nutritional status of schoolchildren aged 10–12 years was shown. The educational program promoted a Mediterranean diet and lifestyle as a healthy and sustainable way of living, important for children's future health and wellbeing. New research-based approaches are needed for making children more aware and capable of handling the complexity of sustainable living.