Abstract Background Although cigarette smoking is a leading cause of death and disability in the United States (US), over 40 million adults in the US currently smoke. Quitting smoking is particularly difficult for smokers with certain types of psychological vulnerability. Researchers have frequently called attention to the relation between smoking and anxiety-related states and disorders, and evidence suggests that panic and related anxiety vulnerability factors, specifically anxiety sensitivity (AS or fear of somatic arousal), negatively impact cessation. Accordingly, there is merit to targeting AS among smokers to improve cessation outcome. Aerobic exercise has emerged as a promising aid for smoking cessation for this high-risk (for relapse) group because exercise can effectively reduce AS and other factors predicting smoking relapse (for example, withdrawal, depressed mood, anxiety), and it has shown initial efficacy for smoking cessation. The current manuscript presents the rationale, study design and procedures, and design considerations of the Smoking Termination Enhancement Project (STEP). Methods STEP is a randomized clinical trial that compares a vigorous-intensity exercise intervention to a health and wellness education intervention as an aid for smoking cessation in adults with elevated AS. One hundred and fifty eligible participants will receive standard treatment (ST) for smoking cessation that includes cognitive behavioral therapy (CBT) and nicotine replacement therapy (NRT). In addition, participants will be randomly assigned to either an exercise intervention (ST+EX) or a health and wellness education intervention (ST+CTRL). Participants in both arms will meet 3 times a week for 15 weeks, receiving CBT once a week for the first 7 weeks, and 3 supervised exercise or health and wellness education sessions (depending on randomization) per week for the full 15-week intervention. Participants will be asked to set a quit date for 6 weeks after the baseline visit, and smoking cessation outcomes as well as putative mediator variables will be measured up to 6 months following the quit date. Discussion The primary objective of STEP is to evaluate whether vigorous-intensity exercise can aid smoking cessation in anxiety vulnerable adults. If effective, the use of vigorous-intensity exercise as a component of smoking cessation interventions would have a significant public health impact. Specifically, in addition to improving smoking cessation treatment outcome, exercise is expected to offer benefits to overall health, which may be particularly important for smokers. The study is also designed to test putative mediators of the intervention effects and therefore has the potential to advance the understanding of exercise-anxiety-smoking relations and guide future research on this topic. Clinical trials registry ClinicalTrials.gov, NCT01065506, http://clinicaltrials.gov/ct2/show/NCT01065506