© 2016, Springer Science+Business Media New York. Purpose: Research showing a link between exercise-induced changes in aerobic fitness and reduced fatigue after a cancer diagnosis has been inconsistent. We evaluated associations of fatigue and rate-pressure product (RPP), a reliable index of myocardial oxygen demand, at rest and during submaximal walking following a physical activity intervention among post-primary treatment breast cancer survivors (BCS). Methods: Secondary analyses of 152 BCS in a randomized controlled trial testing a physical activity intervention (INT) versus usual care (UC) were performed. The INT group completed counseling/group discussions along with supervised exercise sessions tapered to unsupervised exercise. Evaluations were made at baseline and immediately post-intervention (M3) on measures of physical activity (accelerometry), graded walk test, and average fatigue over the previous 7 days. RPP was calculated by dividing the product of heart rate and systolic blood pressure by 100. Results: Resting and submaximal RPPs were significantly improved in both groups at M3; however, the magnitude of change (∆) was greater in the INT group from stage 1 (∆RPP1; INT −13 ± 17 vs. UC −7 ± 18; p = 0.03) through stage 4 (∆RPP4; INT −21 ± 26 vs. UC −9 ± 24; p < 0.01) of the walk test. The INT group reported significantly reduced fatigue (INT −0.7 ± 2.0 vs. UC +0.1 ± 2.0; p = 0.02) which was positively associated with ∆RPP during stages 2–4 of the walk test but not ∆aerobic fitness. Conclusions: Lower RPP during submaximal walking was significantly associated with reduced fatigue in BCS. Implications for Cancer Survivors: Exercise/physical activity training programs that lower the physiological strain during submaximal walking may produce the largest improvements in reported fatigue.