A healthy diet is important for optimal child growth and development. School-based opportunities to encourage children to achieve healthy eating behaviors should be explored. Nutrition education programs can provide school children with classroom-based nutrition education and access to fruits and vegetables (FV). However, the effectiveness of specific program components implemented separately has not yet been comprehensively evaluated. The current study examined effectiveness of individual components of two programs targeting primary school children (n = 1460, n = 37 schools) aged 7–12 years. Nutrition knowledge and FV consumption were measured using a student questionnaire, and presence of school food policies was measured in the teachers’ questionnaire. A quasi-experimental design with three arms compared: (1) schools that implemented both programs: FV provision + education (n = 15), (2) schools that implemented the FV provision program only (n = 12), (3) schools that did not implement either program (n = 10). Outcomes were assessed pre-intervention (T0), during the intervention (T1), and 6 months post-intervention (T2). Results indicated a significant increase in nutrition knowledge for children attending schools that had participated in both programs, compared to control schools (p < 0.01), but no significant increase in FV intake. In schools without food policies, FV provision alone contributed to an increase in child FV intake (p < 0.05).