Abstract Background Guidelines recommend offering cessation interventions to smokers eligible for lung cancer screening, but there is little data comparing specific cessation approaches in this setting. We compared the benefits and costs of different smoking cessation interventions to help screening programs select specific cessation approaches. Methods We conducted a societal-perspective cost-effectiveness analysis using a Cancer Intervention and Surveillance Modeling Network model simulating individuals born in 1960 over their lifetimes. Model inputs were derived from Medicare, national cancer registries, published studies, and micro-costing of cessation interventions. We modeled annual lung cancer screening following 2014 US Preventive Services Task Force guidelines plus cessation interventions offered to current smokers at first screen, including pharmacotherapy only or pharmacotherapy with electronic and/or web-based, telephone, individual, or group counseling. Outcomes included lung cancer cases and deaths, life-years saved, quality-adjusted life-years (QALYs) saved, costs, and incremental cost-effectiveness ratios. Results Compared with screening alone, all cessation interventions decreased cases of and deaths from lung cancer. Compared incrementally, efficient cessation strategies included pharmacotherapy with either web-based cessation ($555 per QALY), telephone counseling ($7562 per QALY), or individual counseling ($35 531 per QALY). Cessation interventions continued to have costs per QALY well below accepted willingness to pay thresholds even with the lowest intervention effects and was more cost-effective in cohorts with higher smoking prevalence. Conclusion All smoking cessation interventions delivered with lung cancer screening are likely to provide benefits at reasonable costs. Because the differences between approaches were small, the choice of intervention should be guided by practical concerns such as staff training and availability.