Background: Aerobic exercise, either continuous or high intensity interval training (HIIT), induces important benefits in chronic heart failure (CHF) patients. Resistance training has been also shown to be beneficial in CHF. However, data regarding combined aerobic exercise and muscle strength training is still limited. The aim of this study was to investigate whether adding strength training to a HIIT protocol within a cardiac rehabilitation (CR) program has a cumulative beneficial effect on the functional capacity (FC) and quality of life (QoL) in patients with CHF. Methods: Forty-four consecutive patients [35 males, ejection fraction (EF) 50%] with CHF under medication enrolled in a 36-session CR program and were randomized in two exercise groups; HIIT (HIIT group) or HIIT combined with strength training (high intensity interval training combined with strength training (COM) group). All patients underwent baseline and endpoint outcome measures of a symptom-limited maximal cardiopulmonary exercise testing (CPET), 1 repetition maximum (1RM) test, muscular endurance test, echocardiography, and Minnesota Living with Heart Failure Questionnaire (MLWHFQ). Results: Most of the CPET indices, EF, 1RM test, muscular endurance and QoL were improved after the CR program in each exercise training group (p 0.05). However, COM group demonstrated a further improvement in chest muscle testing and workload at anaerobic threshold (AT) compared to HIIT group. Conclusions: An exercise-based CR program, consisted of either HIIT or HIIT combined with strength training, improves FC and QoL of patients with CHF. However, the addition of strength training to HIIT seems to have further beneficial effects on chest muscle strength and endurance, as well as workload at AT. Clinical Trial Registration: The study was registered in ClinicalTrials.gov with number NCT02387411.