Current treatment guidelines recommend that all smokers be given motivational or action-oriented counseling, as is appropriate to their readiness to quit smoking. The present study assessed the acceptability and impact of a proactively delivered, motivationally tailored phone counseling program targeted to women with elevated risk for cervical cancer. Female smokers with a recent abnormal pap exam or a colposcopy were contacted and invited to participate, regardless of their interest in quitting smoking. Participants were randomly assigned to usual care (UC) or UC plus motivationally enhanced phone counseling (MEC). The intervention was well received: 79% of eligible women enrolled (n = 275), and 90% completed at least three of four calls. Participation did not vary by baseline motivation to quit. Compared with control subjects, counseling participants were more likely to seek additional treatment services and had a higher 7-day point-prevalence abstinence rate at 6 months (20% MEC vs. 12% UC, p<.05). MEC impact was sustained at 12 months, but abstinence increased among the UC group (18% MEC vs. 20% UC, p = ns). There was no difference in repeated point-prevalence abstinence at 6 and 12 months (11% MEC vs. 10% UC, p = ns). Outcomes were similar in a subgroup of 229 women who, at baseline, were interested in quitting in the next 6 months.