Heart rate variability (HRV), a marker of cardiovascular health, declines with aging and physical inactivity. We compared the effects of supramaximal high-intensity interval training (HIT) with brief intervals and moderate-intensity training (MIT) on HRV in non-exercising older adults. Sixty-eight participants were randomized to 12 weeks of supervised cycling performed twice weekly: supramaximal HIT (10 × 6-s intervals) or MIT (3 × 8-min intervals), with training intensity individually prescribed and progressively increased over the intervention using external power output. HRV was assessed using time-domain indices (SDNN, RMSSD, and LnRMSSD) and resting heart rate from 5-min segments, derived from 10-min recordings collected in participants' homes on seven consecutive days at baseline and follow-up. Between-group differences in change favored supramaximal HIT for SDNN (5.4 ms [95% CI: 1.1–9.7]), RMSSD (3.5 ms [0.7–6.3]), and LnRMSSD (0.15 [0.01–0.28]). Within-group changes showed an increase in RMSSD in the HIT group (2.0 ms [0.1–4.0]) and a decrease in SDNN in the MIT group (−3.1 ms [−6.2 to −0.1]). Resting heart rate did not differ between groups. In conclusion, supramaximal HIT induced more favorable HRV adaptations than MIT in non-exercising older adults.