Background: Increased physical activity and fruit and vegetable (FV) intake are typically suggested to counter obesity. Sustained behavior change in those areas has, however, been poor, possibly because of a lack of understanding of the effects of psychosocial factors. Using data from previous research, this study aimed to better define the role of physical activity and FV intake in short- and long-term weight loss via changes in malleable psychosocial mediators and moderators. Methods: Women who were obese (n = 183; age = 50.0 ± 7.9 years; body mass index = 35.2 ± 3.2 kg/m2, mean ± SD) and who previously participated in 3 different community-based behavioral weight-loss treatments were assessed over 2 years. Changes in FV intake, physical activity, self-regulation of physical activity and eating (aggregated), negative mood, and weight were measured over 6 and 24 months. Results: Changes in each variable over both 6 and 24 months were significant (all p values <0.001). The FV intake to the weight-related caloric intake relationship (β = −0.30, p < 0.001) was significantly mediated by self-regulation change over 6 months. The physical activity to weight-change relationship (β = −0.46, p < 0.001) was significantly mediated by both self-regulation and mood change over 24 months. Physical activity, itself, accounted for only 16% of weight-related caloric expenditure differences. Changes in physical activity and FV intake were each independent predictors of weight change over 24 months (overall R2 = 0.50, p < 0.001). Conclusion: Findings clarified theory-based targets for weight-management treatments and suggested that future weight-loss treatments strongly focus on developing self-regulatory skills to address barriers to behavioral changes.