We investigated whether a combination of mild calorie restriction (MCR) and high-intensity interval walking (HIW) improved physical fitness more than HIW alone in middle-aged and older overweight Japanese (40-69 years old, BMI >= 23.6 kg/m(2)). Forty-seven women and 16 men were divided into MCR + HIW and HIW groups. All subjects performed HIW: >= 5 sets of 3-min low-intensity walking (40% peak aerobic capacity for walking, VO2peak) and 3-min high-intensity walking (>= 70% VO2peak) per day, >= 4 days per week, for 16 weeks while energy expenditure was monitored with a tri-axial accelerometer. The MCR + HIW group consumed meal replacement formula (240 kcal): a mixture of low-carbohydrates and -fat and high-protein, for either lunch or dinner everyday and therefore, had similar to 87% of the energy intake of the HIW group during the intervention period. Although the HIW group showed improvements in BMI, blood pressure, and several blood chemicals, the MCR + HIW group had greater improvement. Moreover, the medical expenditure for the 6 months including the intervention period was 59% lower in the MCR + HIW group than in the HIW group. Our strategy of a short-term combination of MCR and HIW may thus prevent lifestyle-associated diseases and improve health in middle-aged and older overweight Japanese.