The objective of the study was to develop a novel procedure to increase self-efficacy for exercise. Gains in one’s ability to resolve day-to-day obstacles for entering an exercise routine were expected to cause an increase in self-efficacy for exercise. Fifty-five sedentary participants (did not exercise regularly for at least 4 months prior to the study) who expressed an intention to exercise in the near future were selected for the study. Participants were randomly assigned to one of three conditions: (1) an Experimental Group in which they received a problem-solving training session to learn new strategies for solving day-to-day obstacles that interfere with exercise, (2) a Control Group with Problem-Solving Training which received a problem-solving training session focused on a typical day-to-day problem unrelated to exercise, or (3) a Control Group which did not receive any problem-solving training. Assessment of obstacles to exercise and perceived self-efficacy for exercise were conducted at baseline; perceived self-efficacy for exercise was reassessed post-intervention (1 week later). No differences in perceived challenges posed by obstacles to exercise or self-efficacy for exercise were observed across groups at baseline. The Experimental Group reported greater improvement in self-efficacy for exercise compared to the Control Group with Training and the Control Group. Results of this study suggest that a novel procedure that focuses on removing obstacles to intended planned fitness activities is effective in increasing self-efficacy to engage in exercise among sedentary adults. Implications of these findings for use in applied settings and treatment studies are discussed.