© 2017, Springer-Verlag GmbH Germany, part of Springer Nature. Purpose: We hypothesized exercise training-induced improvements in ease of walking would associate with favorable changes in objectively measured physical activity (PA) and self-reported depressive symptoms following a PA behavior-change intervention in non-metastatic breast cancer survivors (BCS). Methods: Twenty-seven BCS received random assignment to an intervention (INT) or control group (CON). INT included counseling/group discussions coupled with supervised exercise tapered to unsupervised exercise. PA, depressive symptoms, and ease of walking were evaluated pre-/post-intervention using 10-day accelerometry, HADS depression subscale, and indirect calorimetry during a standardized treadmill test, respectively. PA composite score was calculated by converting weekly minutes of moderate-to-vigorous PA and average steps/day to z-scores then dividing the sum by 2. Cardiac efficiency was determined by dividing steady-state oxygen uptake by heart rate to evaluate the volume of oxygen consumed per heartbeat. Results: ANCOVA revealed a significant time by group interaction showing the INT group exhibited greater positive changes in the PA composite compared to the CON (INT, + 0.14 ± 0.66 au vs. CON, − 0.48 ± 0.49 au; p = 0.019; ηp2 = 0.21). Changes occurring from baseline to follow-up, among all participants, revealed improved ease of walking (less oxygen uptake) associated with increased PA composite (r = − 0.52; p = 0.010) and lower depressive symptomology (r = 0.50; p = 0.012) adjusted for age, race, and months since cancer diagnosis. Increased cardiac efficiency during the standardized treadmill test also associated with less daily sedentary time (r = − 0.52; p = 0.021). Conclusions: These data support the assertion that reducing the physiological difficulty of walking may contribute to greater engagement in free-living PA, less sedentary time, and decreased psychosocial distress among BCS.