Preventing young people's cigarette smoking is a major public health priority, and smoking is especially prevalent in vocational schools. Well-enforced comprehensive school tobacco policies accompanied by preventive efforts show potential to reduce smoking, but the implementation process is crucial to achieve the intended effect. We investigate whether and how implementation fidelity of a multi-component smoking prevention intervention impacted student smoking outcomes after 4-5 months among students in Danish vocational education and training (national age range 15-65 years, mean 25.6) and preparatory basic education (national age range 15-25 years, mean 17.6) institutions using questionnaire data from a cluster-RCT. The intervention included a smoke-free school hours policy, educational curriculum, and class competition. We calculated an overall implementation fidelity measure combining staff-reported school-level delivery (fidelity) and student-reported receipt (participation, responsiveness), and used multilevel regression models to analyze associations with smoking outcomes (smoking daily, regularly, and during school hours). We supplemented the analysis with restricted cubic spline regression. Additionally, we stratified the analyses by school types and analyzed associations between implementation fidelity of the separate intervention components and smoking outcomes. High implementation was associated with lower odds of regular smoking (OR: 0.37, 95% CI: 0.18-0.78) and smoking during school hours, but not daily smoking, and these associations varied between the school settings. When analyzed separately, implementation fidelity of the components did not affect the outcomes significantly. Our findings underline the need to support the implementation process of school tobacco policy interventions to ensure the intended effects of reducing students' smoking.