Background: After an increase in cigarette taxes and implementation of smoke-free workplace legislation, the New York City Department of Health and Mental Hygiene, the New York State Department of Health, and the Roswell Park Cancer Institute undertook large-scale distribution of free nicotine replacement therapy (NRT). We did a 6 month follow-up survey to assess the success of this programme in improving smoking cessation on a population basis. Methods: 34 090 eligible smokers who phoned a toll-free quitline were sent a 6-week course of nicotine patches (2 weeks each of 21 mg, 14 mg, and 7 mg per day). Brief follow-up counselling calls were attempted. At 6 months after treatment, we assessed smoking status of 1305 randomly sampled NRT recipients and a non-randomly selected comparison group of eligible smokers who, because of mailing errors, did not receive the treatment. NRT recipients were compared with local survey-derived data for heavy smokers in New York City. Findings: An estimated 5% of all adults in New York City who smoked ten cigarettes or more daily received NRT; most (64%) recipients were non-white, foreign-born, or resided in a low-income neighbourhood. Of individuals contacted at 6 months, more NRT recipients than comparison group members successfully quit smoking (33% vs 6%, p<0·0001), and this difference remained significant after adjustment for demographic factors and amount smoked (odds ratio 8·8, 95% CI 4·4-17·8). Highest quit rates were associated with those who were foreign born (87 [39%]), older than 65 years (40 [47%]), and smoked less than 20 cigarettes per day (116 [35%]). Those who received a counselling call were more likely to stop smoking than those who did not (246 [38%] vs 189 [27%], p=0·001). With the conservative assumption that every 6-month follow-up survey non-respondent continued to smoke, the stop rate among NRT recipients was 20%. At least 6038 successful quits were attributable to NRT receipt, and cost was US$464 per quit. Interpretation: Easy access to cessation medication for diverse populations could help many more smokers to stop.