Objective: Small-scale pilot testing of supplementing a required college health-related fitness course with a cognitive-behavioral exercise-support protocol (The Coach Approach). Participants: Three classes were randomly assigned to Usual processes (n = 32), Coach Approach-supplemented: Mid-size Groups (n = 32), and Coach Approach-supplemented: Small Groups (n = 34) conditions. Methods: Repeated-measures analyses of variance (ANOVAs) assessed overall and between-class changes in the behavioral/physiological factors of exercise, fruit/vegetable intake, and body mass index (BMI); and the psychosocial factors of self-regulation, exercise self-efficacy, mood, and body satisfaction. Dependent t tests evaluated within-class changes. Multiple regression analyses tested prediction of exercise by changes in self-regulation, self-efficacy, and mood. Results: Significant improvements in self-regulation and fruit/vegetable intake were found in all classes. The Coach Approach-supplemented classes demonstrated significant increases in exercise. Significant improvements in BMI, self-efficacy, and body satisfaction were found in only The Coach Approach-supplemented: Small Groups class. Psychosocial changes predicted increased exercise. Self-regulation was the strongest contributor. Conclusions: Overall, results were positive and warrant more comprehensive testing.