In this study, we examined whether perceived variety in exercise prospectively predicts unique variance in exercise behavior when examined alongside satisfaction of the three basic psychological needs (for competence, relatedness, and autonomy) embedded within self-determination theory (Ryan & Deci, 2002), through the mediating role of autonomous and controlled motivation. A convenience sample of community adults (N = 363) completed online questionnaires twice over a 6-week period. The results of structural equation modeling showed perceived variety and satisfaction of the needs for competence and relatedness to be unique indirect positive predictors of exercise behavior (through autonomous motivation) 6 weeks later. In addition, satisfaction of the need for autonomy was found to negatively predict controlled motivation. Perceived variety in exercise complemented satisfaction of the needs for competence, relatedness, and autonomy in predicting motivation and (indirectly) exercise behavior, and may act as a salient mechanism in the prediction of autonomous motivation and behavior in exercise settings.