Background: Tobacco smoking remains the leading preventable cause of death among American women. Aerobic exercise has shown promise as an aid to smoking cessation because it improves affect and reduces nicotine withdrawal symptoms. Studies outside the realm of smoking cessation have shown that yoga practice also reduces perceived stress and negative affect. Methods: This pilot study examines the feasibility and initial efficacy of yoga as a complementary therapy for smoking cessation. Fifty-five women were given 8-week group-based cognitive behavioral therapy for smoking cessation and were randomized to a twice-weekly program of Vinyasa yoga or a general health and wellness program (contact control). The primary outcome measure was 7-day point prevalence abstinence at the end of treatment validated by saliva cotinine testing. Longitudinal analyses were also conducted to examine the effect of intervention on smoking cessation at 3- and 6-month follow-up. We examined the effects of the intervention on potential mediating variables (e. g., confidence in quitting smoking, self-efficacy), as well as measures of depressive symptoms, anxiety, and perceived health (SF-36). Results: At end of treatment, women in the yoga group had a greater 7-day point-prevalence abstinence rate than controls (odds ratio [OR], 4.56; 95% CI, 1.1-18.6). Abstinence remained higher among yoga participants through the six month assessment (OR, 1.54; 95% CI, 0.34-6.92), although differences were no longer statistically significant. Women participating in the yoga program also showed reduced anxiety and improvements in perceived health and well-being when compared with controls. Conclusions: Yoga may be an efficacious complementary therapy for smoking cessation among women.