Physical activity rates in Canada are poor across adulthood, with rates declining as people get older. With the Canadian population aging, understanding factors related to exercise adherence in older populations is critical. This study determined if three different types of self-efficacy (task, scheduling, and barriers) could predict adherence to an exercise program in middle-aged and older men and women. Adherence data was examined from a subset of women (n = 125; Mage = 66.74 years, SD = 6.29) and men (n = 51; Mage = 69.69 years, SD = 6.46) who participated in a 12-week structured exercise program. Participants were community dwelling, independent walkers with no neural impairments. Hierarchal regressions were conducted, one for each gender. For women, controlling for body mass index (BMI), age and baseline physical activity, the self-efficacy variables accounted for significant variance in adherence, F(6, 118) = 4.19, p < .001, R2adj. = .134. Significant predictors of adherence were physical activity (β = .228, p = .01), barrier self-efficacy (β = .239, p = .02) and scheduling self-efficacy (β = .288, p = .00). For men, controlling for BMI, age and baseline physical activity, the self-efficacy variables accounted for significant variance in adherence, F(6, 44) = 4.30, p = .00, R2adj. = .283. Significant predictors of adherence were age (β = .290, p = .03) and task self-efficacy (β = .425, p = .01). Future research should focus on designing physical activity programs that emphasize increasing types of self-efficacy specific to men and women.