A total of 205 (113 male, 92 female) nonhospitalized recovering alcoholics with > 3 months of continuous abstinence from alcohol and drugs and relatively heavy tobacco dependence (Fagerstrom Tolerance Questionnaire score = 7.7; mean number of cigarettes per day, 26.8; mean number of years smoked, 24.4) were randomized to standard treatment (ST) American Lung Association quit program plus nicotine anonymous meetings (n = 70), behavioral counseling plus physical exercise (BEX; n = 72), or behavioral counseling plus nicotine gum (BNIC; n = 63). A 3 x 4 repeated measures design was used to evaluate the effectiveness of the interventions on smoking outcome at baseline, posttreatment, and 6- and 12-month follow-ups. Self-reported smoking status was verified with biochemical and informant report. Verified self-report indicated that significantly more smokers in BEX quit by posttreatment (60%) than in either BNIC (52%) or ST (31%), chi 2 (2, N = 205) = 17.85, p < .01, but not at the 6-month (29%, 27%, and 21%, respectively) or 12-month (27%, 27%, and 26%, respectively) follow-up. Only 4% (7 of 188) relapsed to alcohol or drugs. Alcohol relapse did not differ by treatment group or smoking status. Length of alcohol abstinence was not associated with smoking cessation outcome.