This study was an outcome evaluation of a multi-component nutrition education program for African American kindergarten and first grade students attending an under-resourced urban school. The program focused on increasing fruit and vegetable knowledge and vegetable consumption during school lunch. It included a classroom-based knowledge change component, a lunchtime-based behavior-change component, and a home component. This program was unique in that natural helpers in the school (i.e., paraprofessionals) were enlisted as agents of behavior change. Findings indicated that the program was considered socially valid from the perspectives of students, teachers, and paraprofessional community assistants. Implementation integrity was acceptable for the classroom intervention, but highly variable for the lunchtime intervention. Program outcomes demonstrated that knowledge change was high, but behavior change was variable. Inconsistent behavioral effects appeared to be related in part to the variable level of intervention integrity. The challenges of promoting intervention integrity with paraprofessionals were discussed, and strategies for improving integrity were outlined.