There is a lack of evidence of the relative cost-effectiveness of proactive telephone counseling (PTC) and Web-based delivery of smoking cessation services in conjunction with pharmacotherapy. We calculated the differential cost-effectiveness of three behavioral smoking cessation modalities with varenicline treatment in a randomized trial of current smokers from a large health system. Eligible participants were randomized to one of three smoking cessation interventions: Web-based counseling (n=401), PTC (n=402), or combined PTC-Web counseling (n=399). All participants received a standard 12-week course of varenicline. The primary outcome was a 7-day point prevalent nonsmoking at the 6month follow-up. The Web intervention was the least expensive followed by the PTC and PTC-Web groups. Costs per additional 6-month nonsmoker and per additional lifetime quitter were $1,278 and $2,601 for Web, $1,472 and $2,995 for PTC, and $1,617 and $3,291 for PTC-Web. Cost per life-year (LY) and quality-adjusted life-year (QALY) saved were $1,148 and $1,136 for Web, $1,320 and $1,308 for PTC, and $1,450 and $1,437 for PTC-Web. Based on the cost per LY and QALY saved, these interventions are among the most cost-effective life-saving medical treatments. Web, PTC, and combined PTC-Web treatments were all highly cost-effective, with the Web treatment being marginally more cost-effective than the PTC or combined PTC-Web treatments.