Purpose Data from large randomized controlled trials confirming sleep quality improvements with aerobic physical activity have heretofore been lacking for post-primary treatment breast cancer survivors. Our primary purpose for this report was to determine the effects of a physical activity behavior change intervention, previously reported to significantly increase physical activity behavior, on sleep quality in post-primary treatment breast cancer survivors. Methods Post-primary treatment breast cancer survivors (n = 222) were randomized to a 3-month physical activity behavior change intervention (Better Exercise Adherence after Treatment for Cancer [BEAT Cancer]) or usual care. Self-report (Pittsburgh Sleep Quality Index [PSQI]) and actigraphy (latency and efficiency) sleep outcomes were measured at baseline, 3 months (M3), and 6 months (M6). Results After adjusting for covariates, BEAT Cancer significantly improved PSQI global sleep quality when compared with usual care at M3 (mean between-group difference [M] = -1.4, 95% confidence interval [CI] = -2.1 to -0.7, P < 0.001) and M6 (M = -1.0, 95% CI = -1.7 to -0.2, P = 0.01). BEAT Cancer improved several PSQI subscales at M3 (sleep quality M = -0.3, 95% CI = -0.4 to -0.1, P = 0.002; sleep disturbances M = -0.2, 95% CI = -0.3 to -0.03, P = 0.016; daytime dysfunction M = -0.2, 95% CI = -0.4 to -0.02, P = 0.027) but not M6. A nonsignificant increase in percent of participants classified as good sleepers occurred. No significant between-group difference was noted for accelerometer latency or efficiency. Conclusion A physical activity intervention significantly reduced perceived global sleep dysfunction at 3 and 6 months, primarily because of improvements in sleep quality aspects not detected with accelerometer.