Behavior change theory was used to explore predictors of long-term adherence (≥2 years) to exercise. A retrospective analysis of data from participants (N = 97) who reached a 6-month follow-up, which served as the baseline, was evaluated for completion of yearly follow-up surveys. Variables examined at baseline, which included age, race, gender, body mass index (BMI), and self-report of comorbidities, symptoms, physical function, and a Barriers Specific Self-Efficacy Scale, were examined with significance set at p < .05. Lower BMI (29.1 ± 5.1 vs. 31.6 ± 6.5, p = .047) and higher self-efficacy to overcome environmental barriers (p = .016) and social isolation (p = .05) were associated with long-term adherence. Self-efficacy to overcome environmental and social barriers, such as inclement weather, access to exercise site, and opportunities for group-based exercise, should be addressed to promote long-term adherence to exercise among older adults.