Background: Using a practical setting, this study aimed to test exercise and nutrition interventions' effects on negative mood, self-regulation, and self-efficacy to control eating; and to assess the ability of mood change to predict changes in eating behavior, while accounting for changes in self-regulation and self-efficacy. Methods: Severely obese adults participated in a cognitive-behavioral exercise support treatment paired with either nutrition education (n = 140) or cognitive-behavioral methods applied to improved eating (n = 146). They were assessed on measures of overall negative mood, self-regulatory skill usage, self-efficacy to control eating when negative moods are present, and fruit and vegetable consumption at baseline and Week 26. Results: Significant improvements in each psychosocial variable and fruit and vegetable intake were found. Improved mood significantly predicted fruit and vegetable consumption change, R2 = 0.12, P < 0.001. Entry of changes in self-regulation and self-efficacy into the multiple regression equation significantly strengthened the variance explained, R2 = 0.18, P < 0.001. Discussion: Findings suggest that exercise-induced improvements in mood improve eating behaviors, with increases in self-regulation and self-efficacy adding to this effect. © 2013, Baywood Publishing Co., Inc.