In Western culture, evidence has shown that in women with breast cancer exercise decreases fatigue and improves quality of life. However, only 1 pilot study about the effect of exercise has been examined in the Asian breast cancer population that indicated feasibility. Therefore, it is important to further study the effect of an exercise program for Taiwanese women with breast cancer. The purpose of this study was to test the effects of a walking program on Taiwanese women newly diagnosed with early-stage breast cancer. This was an experimental, longitudinal study with 4-time repeated measures based on Banduras Self-efficacy Theory, with the aim of implementing interventions to boost exercise self-efficacy and to evaluate research outcomes. SPSS 17.0 with descriptive statistics using frequency, percentage, mean, and SD as well as inferential statistics such as t test, χ test, hierarchical linear model, repeated-measures analysis of variance, and analysis of covariance was used for data analysis. Results of this study indicated that subjects in the exercise group had significantly better quality of life, less fatigue, less sleep disturbances, higher exercise self-efficacy, more exercise behavior, and better exercise capacity compared with those in the usual-care group after the intervention. This program was effective and feasible, but more research studies with experimental, longitudinal design to verify the effects of this exercise program on Taiwanese women with breast cancer will be needed. Nurses, depending on skill and knowledge, can encourage physical activity, refer patients to rehabilitation programs, and prescribe and monitor exercise in breast cancer population.