Background: Tobacco users receiving behavioural and pharmacological assistance are more likely to quit. Although telephone quitlines provide population access to counselling, few offer pharmacotherapy. Objective: To assess change in cessation rates and programme impact after the addition of free nicotine replacement therapy (NRT) to statewide quitline services. Design, setting, participants: An observational study of cohorts of callers to the Minnesota QUITPLANSM Helpline before (n = 380) and after (n = 373) the addition of access to free NRT. Intervention: Mailing of NRT (patch or gum) to callers enrolling in multi-session counselling. Main outcome measure: Thirty-day abstinence six months after programme registration. Results: The number of callers increased from 155 (SD 75) to 679 (180) per month pre-NRT to post-NRT (difference 524, 95% confidence interval (CI) 323 to 725). Post-NRT, the proportion of callers enrolling in multi-session counselling (23.4% v 90.1%, difference 66.6%, 95% CI 60.8% to 71.6%) and using pharmacotherapy (46.8% v 86.8%, difference 40.0%, 95% CI 31.3% to 47.9%) increased. Thirty-day abstinence at six months increased from 10.0% pre-NRT to 18.2% post-NRT (difference 8.2%, 95% CI 3.1% to 13.4%). Post-NRT the average number of new ex-smokers per month among registrants increased from 15.5 to 123.6 (difference 108.1, 95% CI 61.1 to 155.0). The cost per quit pre-NRT was $1362 (SD $207). The cost per quit post-NRT was $1934 ($215) suggesting a possible increase in cost per quit (difference $572, 95% CI - $12 to $1157). Conclusion: The addition of free NRT to a state quitline is followed by increases in participation and abstinence rates resulting in an eightfold increase in programme impact. These findings support the addition of access to pharmacological therapy as part of state quitline services.