The incremental effects of (a) a self-help booklet alone, (b) self-help booklet with computer-generated personalized feedback, and (c) self-help booklet, personalized feedback, and outreach telephone counseling were evaluated in a population-based, nonvolunteer sample of smokers. Smokers (N = 1,137) were identified through a telephone survey of a random sample of 5,903 enrollees in a health maintenance organization and randomized to a no-treatment control group or 1 of the 3 intervention conditions. Smoking status was ascertained 3, 12, and 21 months postrandomization. Cotinine validation of self-reported cessation was obtained at the 12-month follow-up. Overall, the telephone counseling significantly increased smoking cessation at the 3-month follow-up, but not at 12 or 21 months. Among smokers who were precontemplative at baseline, telephone counseling significantly increased prevalent abstinence at 3 and 12 months and continuous abstinence at 21 months (defined as self-reported abstinence at 3, 12, and 21 months).