Objective: To assess the relative cost-effectiveness of various non-television advertising media in encouraging 25-39 year-old male smokers to respond to a cessation-related call to action. Information about how new electronic media compare in effectiveness is important to inform the implementation of future tobacco control media campaigns. Methods: Two testimonial advertisements featuring members of the target group were developed for radio, press and online media. Multiple waves of media activity were scheduled over a period of seven weeks, including an initial integrated period that included all three media and subsequent single media phases that were interspersed with a week of no media activity. The resulting Quit website hits, Quitline telephone calls, and registrations to online and telephone counselling services were compared to advertising costs to determine the relative cost-effectiveness of each media in isolation and the integrated approach. Results: The online-only campaign phase was substantially more cost-effective than the other phases, including the integrated approach. Conclusions: This finding is contrary to the current assumption that the use of a consistent message across multiple media simultaneously is the most cost-effective way of reaching and affecting target audiences. Implications: Online advertising may be a highly cost-effective channel for low-budget tobacco control media campaigns.