We investigated the changes of an 8-week cardiac rehabilitation (CR) program on physiological outcomes and health-related quality of life (HRQL) in Japanese cardiac surgery patients. Subjects were 47 consecutive outpatients (32 men, 15 women; mean age 59.4 ± 12.6 years) recovering from cardiac surgery. Patients performed both aerobic exercise on a treadmill at anaerobic threshold intensity and moderate resistance training 2 days per week, 60 min per session, from 1 to 3 months after cardiac surgery. Differences in the eight SF-36 subscale scores and physiological outcomes within the patient group at 1 month and at 3 months after cardiac surgery were analyzed. Peak oxygen uptake, handgrip strength, and knee extension strength were used as physiological outcome measures. HRQL was assessed with the Japanese version Medical Outcome Study Short Form 36 (SF-36). Significant change in overall physiological outcome from 1 month to 3 months was observed. There was also significant change in seven of the eight SF-36 health status subscale scores (physical functioning, role-physical, bodily pain, general health, vitality, role-emotional, and mental health). However, with the exception of physical functioning and mental health scores, values did not reach those of the average healthy Japanese. In conclusion, we found that CR exercise training for Japanese cardiac surgery patients during the recovery phase changes not only physiological outcomes but also HRQL as assessed by the SF-36.