Whereas telephone-based counseling has been found to be effective in supporting smokers interested in quitting smoking, it is not known whether proactive efforts to reach smokers receiving cessation medications will enhance their likelihood of successful quitting. We had an opportunity to test, in a health plan setting, an offer of telephone-based counseling with smokers identified from health plan records as recently filling a prescription for nicotine replacement therapy or bupropion. After we removed 31 members determined to be ineligible, 1,329 were randomly allocated to receive an invitation either to telephone-based counseling (n = 663) or to a control group (n = 666). On average, 7 days (range = 3-15 days) elapsed from the day of the prescription fill until the Center for Health Promotion began calling to invite members to participate in telephone counseling. The Center for Health Promotion was able to reach 49% of those in the intervention group (323/663). Of these members, 118 (37%) declined any participation. Therefore, in response to the proactive contact, 63% (205/323) of those reached and 31% (205/663) of those eligible participated in some smoking cessation counseling. At the 3-month follow-up, we observed an increased quit rate (33.1% vs. 27.4%) among health plan members randomized to telephone-based smoking cessation counseling. The results varied by gender and amount smoked. In addition, the variables associated with quitting in a multivariate logistic regression model included older age and using more than 30 days of medication.