Despite increasing numbers of cancer survivors and evidence that diet and physical activity improves the health of cancer survivors, most do not meet guidelines. Some social cognitive theory (SCT)-based interventions have increased physical activity behavior, however few have used objective physical activity measures. The Exercise and Nutrition Routine Improving Cancer Health (ENRICH) randomized controlled trial reported a significant intervention effect for the primary outcome of pedometer-assessed step counts at post-test (8-weeks) and follow-up (20-weeks). The aim of this study was to test whether the SCT constructs operationalized in the ENRICH intervention were mediators of physical activity behavior change. Randomized controlled trial with 174 cancer survivors and carers assessed at baseline, post-test (8-weeks), and follow-up (20-weeks). Participants were randomized to the ENRICH six session face-to-face healthy lifestyle program, or to a wait-list control. Hypothesized SCT mediators of physical activity behavior change (self-efficacy, behavioral goal, outcome expectations, impediments, and social expectations) were assessed using valid and reliable scales. Mediation was assessed using the Preacher and Hayes SPSS INDIRECT macro. At eight weeks, there was a significant intervention effect on behavioral goal (A = 9.12, p = 0.031) and outcome expectations (A = 0.25, p = 0.042). At 20 weeks, the intervention had a significant effect on self-efficacy (A = 0.31, p = 0.049) and behavioral goal (A = 13.15, p = 0.011). Only changes in social support were significantly associated with changes in step counts at eight weeks (B = 633.81, p = 0.023). Behavioral goal was the only SCT construct that had a significant mediating effect on step counts, and explained 22 % of the intervention effect at 20 weeks (AB = 397.9, 95 % CI 81.5-1025.5). SCT constructs had limited impact on objectively-assessed step counts in a multiple health behavior change intervention for cancer survivors and their carers. Behavioral goal measured post-intervention was a significant mediator of pedometer-assessed step counts at 3-months after intervention completion, and explained 22 % of the intervention effect. Future research should examine the separate impact of goals and planning, as well as examining mediators of behavior maintenance in physical activity interventions targeting cancer survivors. Australian and New Zealand Clinical Trials registry ANZCTRN1260901086257 .