Introduction This study investigates the effect of a modest weight loss either by a calorie restricted diet or mainly by increased physical exercise on health related quality of life (HRQoL) in overweight-to-obese and inactive postmenopausal women. We hypothesize that HRQoL improves with weight loss, and that exercise-induced weight loss is more effective for this than diet-induced weight loss. Methods The SHAPE-2 trial was primarily designed to evaluate any additional effect of weight loss by exercise compared with a comparable amount of weight loss by diet on biomarkers relevant for breast cancer risk. In the present analysis we focus on HRQoL. We randomly assigned 243 eligible women to a diet (n = 97), exercise (n = 98), or control group (n = 48). Both interventions aimed for 5–6 kg weight loss. HRQoL was measured at baseline and after 16 weeks by the SF-36 questionnaire. Results Data of 214 women were available for analysis. Weight loss was 4.9 kg (6.1%) and 5.5 kg (6.9%) with diet and exercise, respectively. Scores of the SF-36 domain ‘health change’ increased significantly by 8.8 points (95% CI 1.6;16.1) with diet, and by 20.5 points (95% CI 13.2;27.7) with exercise when compared with control. Direct comparison of diet and exercise showed a statistically significantly stronger improvement with exercise. Both intervention groups showed a tendency towards improvements in most other domains, which were more pronounced in the exercise group, but not statistically different from control or each other. Conclusion In a randomized trial in overweight-to-obese and inactive postmenopausal women a comparable 6%-7% weight loss was achieved by diet-only or mainly by exercise and showed improvements in physical and mental HRQoL domains, but results were not statistically significant in either the diet or exercise group. However, a modest weight loss does lead to a positive change in self-perceived health status. This effect was significantly larger with exercise-induced weight loss than with comparable diet-induced weight loss.