Implementation of vegetable and fruit programs in schools is less than optimal. This study aimed to identify, using a theoretical framework, factors associated with implementation of a school vegetable and fruit program; that provides a time in class for children to consume a piece of vegetable or fruit they have brought from home. Three hundred and three randomly selected school principals across the state of New South Wales, Australia responded to a 25-min telephone survey. Principals were asked if their school had implemented a vegetable and fruit program, and which of 12 factors from Damschroder's consolidated framework for implementation research had facilitated or impeded implementation. Multiple logistic regression models examined the association between such factors and program implementation. Seventy-eight percent of schools had a vegetable and fruit program. Schools were significantly more likely to implement the program if the principal believed that: the program was effective (OR = 2.97; P < 0.02); they had sufficient resources to implement the program (OR = 4.22; P < 0.0001); the program would not be difficult to implement (OR = 10.16; P< 0.0001) and that the program was as important as other school priorities (OR = 2.45; P < 0.02). Realizing the intended benefits of vegetable and fruit programs requires widespread implementation by schools. Consideration of principal beliefs about the program effectiveness, resources, difficultly and relative importance in program implementation strategies appear key to increasing program implementation.