In order to enhance the effectiveness of exercise referral schemes (ERS), further understanding is required of the important predictors of successful adherence to inform future interventions. The present study aimed to explain ERS adherence through examining social cognitive factors in the early stages of the scheme. A prospective cross-sectional design was employed with adults referred to an 8-week ERS completing self-report measures across multiple social cognitive variables at baseline (N = 124) and mid-scheme (N = 58). Findings demonstrated that baseline social cognitive factors were not significantly related to overall ERS adherence. However, when measured at mid-scheme, goal-setting, scheduling self-efficacy, barrier self-efficacy and social support from family were significant correlates of adherence, with changes in social cognitive factors from baseline to mid-scheme combining to explain 22% of the variance in ERS adherence. Our findings provide evidence for early improvements in social cognitive constructs explaining total ERS adherence, thus highlighting their importance in the initial stages of an ERS.