Feasibly implemented Web-based smoking media literacy (SML) programs have been associated with improving SML skills among adolescents. However, prior evaluations have generally had weak experimental designs. We aimed to examine program efficacy using a more rigorous crossover design. Seventy-two ninth grade students completed a Web-based SML program based on health behavior theory and implemented using a two-group two-period crossover design. Students were randomly assigned by classroom to receive media literacy or control interventions in different sequences. They were assessed three times, at baseline (T0), an initial follow-up after the first intervention (T1) and a second follow-up after the second intervention (T2). Crossover analysis using analysis of variance demonstrated significant intervention coefficients, indicating that the SML condition was superior to control for the primary outcome of total SML (F = 11.99; P < 0.001) and for seven of the nine individual SML items. Results were consistent in sensitivity analyses conducted using non-parametric methods. There were changes in some exploratory theory-based outcomes including attitudes and normative beliefs but not others. In conclusion, while strength of the design of this study supports and extends prior findings around effectiveness of SML programs, influences on theory-based mediators of smoking should be further explored.