School tobacco policies are often poorly implemented, which may explain their limited effectiveness. Further, constructs to measure implementation outcomes of school tobacco policies are missing. The Smoke-Free Vocational Schools intervention was designed to stimulate the implementation of a comprehensive school tobacco policy into routine practice. This study (1) developed implementation fidelity outcomes measures for the school tobacco policy and (2) examined associations between intervention activities and implementation fidelity at two time points. We applied a repeated cross-sectional survey study design across seven schools: the first time point was >5 months after the policy was established and the second time point > 14 months after policy establishment. The dependent/outcome variables were four binary fidelity domains as well as a total score across domains. A total of six intervention activities were measured among either students (e.g., new school-break facilities) or staff/managers (e.g., a joint workshop before policy implementation). Associations were analyzed separately for students and staff/managers using generalized linear mixed models, adjusted for confounders. A total of n = 2674 students and n = 871 staff/managers participated. The total implementation fidelity scores increased over time among both students and staff/managers. Three intervention activities were consistently associated with the total implementation fidelity score, including: new school-break facilities (BT1 = 0.08, 95% CI = 0.03; 0.12; BT2 = 0.07, 95% CI = 0.04–0.50), the joint workshop before policy implementation (BT1 = 0.13, 95% CI = 0.02; 0.25; BT2 = 0.13, 95% CI = 0.004; 0.24), and internalization of fixed procedures for enforcement (BT1 = 0.19, 95% CI = 0.13–0.26; BT2 = 0.16, 95% CI = 0.13–0.26). These findings can be applied by schools and other actors in practice. The developed implementation fidelity outcomes measures can be applied in future research on school tobacco policies.