Decreased heart rate variability and attenuated heart rate recovery following exercise are associated with an increased risk of mortality in cardiac patients. This study investigated the effects of 12 weeks of moderate-intensity endurance exercise (END) and a novel low-volume high-intensity interval exercise protocol (HIT) on measures of heart rate recovery and heart rate variability in patients with coronary artery disease (CAD). Fourteen males with CAD participated in 12 weeks of END or HIT training, each consisting of 2 supervised exercise sessions per week. END consisted of 30–50 min of continuous cycling at 60% peak power output (PPO). HIT involved ten 1-min intervals at 88% PPO separated by 1-min intervals at 10% PPO. Heart rate recovery at 1 min and 2 min was measured before and after training (pre- and post-training, respectively) using a submaximal exercise bout. Resting time and spectral and nonlinear domain measures of heart rate variability were calculated. Following 12 weeks of END and HIT, there was no change in heart rate recovery at 1 min (END, 40 ± 12 beats·min−1 vs. 37 ± 19 beats·min−1; HIT, 31 ± 8 beats·min−1 vs. 35 ± 8 beats·min−1; p ≥ 0.05 for pre- vs. post-training) or 2 min (END, 44 ± 18 beats·min−1 vs. 43 ± 19 beats·min−1; HIT, 42 ± 10 beats·min−1 vs. 50 ± 6 beats·min−1; p ≥ 0.05 for pre- vs. post-training). All heart rate variability indices were unchanged following END and HIT training. In conclusion, neither END nor HIT exercise programs elicited training-induced improvements in cardiac autonomic function in patients with CAD. The absence of improvements with training may be attributed to the optimal medical management and normative pretraining state of our sample.