Background: Evidence suggests that nutritional factors, such as consumption of fruits and vegetables, along with socioeconomic factors such as parental education level, are associated with asthma prevalence. Our study examined the role of parental education in the association between fruit and vegetable consumption and adolescent asthma. Methods: 1934 adolescents (mean age: 12.7 years, standard deviation: 0.6 years, boys: 47.5%) and their parents were voluntarily enrolled and completed a validated questionnaire assessing current asthma status, fruit and vegetable consumption and parental educational level. Participants were categorized as high or low intake for five food groups: fruits, cooked vegetables, raw vegetables, all vegetables (cooked and raw), and all three food groups together (fruits and all vegetables). Results: Adolescents who were high consumers of all three food groups (fruits, cooked and raw vegetables) were less likely to have asthma, adjusted for several confounders (adjusted odds ratio (aOR): 0.53, 95% confidence interval (CI): 0.25–0.97). Moreover, in adolescents who had parents with tertiary education and were in the high consumption of all three food groups, the inverse association was almost twofold higher than the one for adolescents with parents of primary/secondary education (aOR: 0.35, 95% CI: (0.21–0.89) and aOR: 0.61, 95% CI: (0.47–0.93) respectively). Conclusions: Our findings highlight the importance of the adoption of a diet rich in fruits and vegetables for all asthmatic adolescents and emphasize the important role of parental influences in this association.