Background: Self-efficacy has been associated with adolescent exercise. Previous studies have revealed that self-efficacy is relatively resistant to change. Effective strategies to build self-efficacy among adolescents are needed. Purpose: To describe the changes in self-efficacy and leisure time exercise produced by the "Planning to be Active Curriculum" (PBA). These changes will be studied among insufficiently active and active adolescents. Methods: A treatment/control group design was implemented in 3 rural Appalachian high schools. PBA curriculum was received by the treatment group, and the control group received a sport-based curriculum. Measurements were collected at pretest, mid-intervention, and 2 weeks postintervention. Results: A significant decrease in self-efficacy was produced by PBA for the insufficiently active at intervention midpoint. These scores significantly increased by intervention posttest. This group also reported an increase from 1 to 3 days of moderate-intensity exercise per week. Discussion: Behaviorally based health education programs could produce initial declines in self-efficacy. Skill building assignments over 8 weeks can build self-efficacy for exercise. Translation to Health Education Practice: Health education programs should target behavioral skills over a period of 8 to 10 weeks to overcome short-term declines and build self-efficacy.