Background: Since physical exercise programs have the potential to help cancer patients regain physical fitness and may exert a range of positive consequences for recovery and psychological well-being, the impact of a physical exercise program was investigated in this prospective study. Patients and Methods: Women with primary nonmetastatic breast cancer after a minimum 4-week period post chemotherapy and/or radiotherapy completion were randomly assigned to one of 2 groups: intervention group (IG) (n = 30) and waiting group (WG) (n = 28). The 10-week twice weekly exercise group program consisted of gymnastics, movement games, relaxation, walking, and jogging. Anxiety, depression, body image, and quality of life were measured using standardized questionnaires. Maximal oxygen uptake (VO<sup>2</sup>max/kg) was assessed as a measure of physical fitness. Results: Patients in the IG improved significantly over time with regard to anxiety (p = 0.03, d = 0.45), depression (p = 0.05, d = 0.43), individual body image (p = 0.006, d = 0.44), and VO<sup>2</sup>max/kg (p < 0.001, d = 0.50), whereas no improvements were observed in the WG. However, this randomized controlled trial failed to demonstrate significant intervention effects in quality of life and social body image. Conclusions: This prospective study provided evidence for the effectiveness of a 10-week physical exercise intervention to significantly improve psychosocial wellbeing, individual body image, and physical fitness.