The objective of this research was to investigate whether heart rate variability (HRV)-guided training improves mortality predictors to a greater extent than predefined training in coronary artery disease patients. Twenty-one patients were randomly allocated to the HRV-guided training group (HRV-G) or the predefined training group (PRED-G). They measured their HRV at home daily and trained three times a week for six weeks. Resting heart rate, isolated vagal-related HRV indices (i.e., RMSSD, HF, and SD(1)), weekly averaged RMSSD, heart rate recovery, and maximum oxygen uptake were assessed before and after the training period. There was a statistically significant difference (p = 0.034) in the change in weekly averaged RMSSD in favor of the HRV-G, while no differences were found in the remaining analyzed variables (p > 0.050). Regardless of the training prescription method, exercise training decreased resting heart rate (p = 0.001; -4.10 [95% CI = -6.37--1.82] beats per minute (bpm)), and increased heart rate recovery at 2 min (p = 0.010; 4.33 [95% CI = 1.15-7.52] bpm) and maximum oxygen uptake (p < 0.001; 3.04 [95% CI = 1.70-4.37] mL.kg(-1).min(-1)). HRV-guided training is superior to predefined training in improving vagal-related HRV when methodological factors are accounted for.