The effects of exercise and mild calorie restriction on heart rate variability (HRV) were investigated in 12 mildly obese, normotensive Japanese women aged 45.8±4.2 (SEM) years with a body mass index (BMI) of 27.3±0.4 kg/m². The subjects participated in a 3-month program aimed at increasing physical activity and modifying eating behavior (intervention group). The control group consisted of 12 women (age 50.1±4.8 years, BMI 27.2±0.6 kg/m²) who did not attend the program. The frequency domain of HRV was calculated from 5-min Holter recordings while the subjects rested in a supine position. After 3 months, BMI decreased to 25.0±0.5 kg/m² (p<0.001 vs baseline) in the intervention group, which was accompanied by decreases in body fat mass, waist circumference, serum total cholesterol and triglycerides, and improvement in insulin sensitivity. The mean and SD of the RR intervals, total power, and low and high frequency power of HRV significantly increased after the intervention, whereas no significant changes were seen for the controls. The changes in these HRV variables (calculated by subtracting the baseline values from the follow-up values) negatively correlated with the change in waist circumference, with the Pearson correlation coefficients being between −0.50 and −0.62 (p<0.05). A negative correlation was also seen between the changes in high frequency power and insulin resistance estimated by homeostasis model assessment (r=−0.49, p<0.05). The combination of exercise and mild calorie restriction led to changes in HRV indicative of an improvement in parasympathetic modulation.