Excess body weight at diagnosis and weight gain after breast cancer are associated with poorer long-term prognosis. This study investigated the effects of a lifestyle intervention on body weight and other health outcomes influencing long-term prognosis in overweight women (BMI > 25.0 kg/m2) recovering from early-stage (stage I–III) breast cancer. A total of 90 women treated 3–18 months previously were randomly allocated to a 6-month exercise and hypocaloric healthy eating program (n = 47, aged 55.6 ± 10.2 year) or control group (n = 43, aged 55.9 ± 8.9 year). Women in the intervention group received three supervised exercise sessions per week and individualized dietary advice, supplemented by weekly nutrition seminars. Body weight, waist circumference, waist/hip ratio [WHR], cardiorespiratory fitness, blood biomarkers associated with breast cancer recurrence and cardiovascular disease risk, and quality of life (FACT-B) were assessed at baseline and 6 months. Three-day diet diaries were used to assess macronutrient and energy intakes. A moderate reduction in body weight in the intervention group (median difference from baseline of -1.09 kg; IQR -0.15 to -2.90 kg; p = 0.07) was accompanied by significant reductions in waist circumference (p < 0.001), WHR (p = 0.005), total (p = 0.021) and saturated fat (p = 0.006) intakes, leptin (p = 0.005), total cholesterol (p = 0.046), and resting diastolic blood pressure (p = 0.03). Cardiopulmonary fitness (p < 0.001) and FACT-B quality of life (p = 0.004) also showed significant improvements in the intervention group. These findings suggest that an individualized exercise and a hypocaloric healthy eating program can positively impact upon health outcomes influencing long-term prognosis in overweight women recovering from early-stage breast cancer.