OBJECTIVES: For smoking cessation, physical activity (PA) may help manage withdrawal symptoms, mood, stress, and weight; yet studies of PA as an aid for smoking cessation have been mixed. This study examined: (1) the impact of an extended relapse prevention program on increasing moderate to vigorous PA (MVPA) in adults enrolled in a tobacco cessation treatment trial; (2) whether changes in MVPA were associated with sustained abstinence from smoking; and (3) mechanisms by which MVPA may support sustained abstinence from smoking. METHODS: In a randomized controlled trial conducted from 2003-2006 in San Francisco, California, 407 adult smokers received a 12 week group-based smoking cessation treatment with bupropion and nicotine patch with the quit date set at week 3. At week 12, participants were randomized to no further treatment or to 40 weeks of bupropion or placebo with or without an 11-session relapse prevention intervention of which 2 sessions (held at weeks 16 and 20) focused on PA. Participants receiving the PA intervention (n=163) received a pedometer, counseling to increase steps 10% biweekly towards a 10,000 steps/day goal, and personalized reports graphing progress with individualized goals. The International Physical Activity Questionnaire assessed weekly minutes of MVPA at baseline and weeks 12 and 24. Sustained abstinence from tobacco at week 24 was validated with expired carbon monoxide. RESULTS: In a repeated mixed model analysis, intervention participants significantly increased their MVPA relative to control participants, F(1,475)=3.95, p=.047. Pedometer step counts also increased significantly, t(23)=2.36, p=.027, though only 15% of intervention participants provided 6 weeks of pedometer monitoring. Controlling for treatment condition, increased MVPA predicted sustained smoking abstinence at week 24, odds ratio=1.84 (95% CI: 1.07, 3.05). Among participants with sustained abstinence, increased MVPA was associated with increased vigor (r=0.23, p=.025) and decreased perceived difficulty with staying smoke-free (r=-0.21, p=.038). CONCLUSION: PA promotion as an adjunct to tobacco treatment increases MVPA levels; changes in MVPA predict sustained abstinence, perhaps by improving mood and self-efficacy.