We tested the hypothesis that baseline cardiac autonomic function and its acute response to all-out interval exercise explains individual fitness responses to high-intensity interval training (HIT). Healthy middle-aged sedentary men performed HIT (n=12, 4-6x30s of all-out cycling efforts with 4-min recovery) or aerobic training (AET, n=9, 40-60min at 60% of peak workload in exercise test [Load(peak)]), comprising 6 sessions within 2 weeks. Low (LF) and high frequency (HF) power of R-R interval oscillation were analyzed from data recorded at supine and standing position (5+5min) every morning during the intervention. A significant training effect (p<0.001), without a training*group interaction, was observed in Load(peak) and peak oxygen consumption (VO2peak). Pre-training supine LF/HF ratio, an estimate of sympathovagal balance, correlated with training outcome in Load(peak) (Spearman's rho [r(s)]=-0.74, p=0.006) and VO2peak (r(s)=-0.59, p=0.042) in the HIT but not the AET group. Also, the mean change in the standing LF/HF ratio in the morning after an acute HIT exercise during the 1(st) week of intervention correlated with training response in Load(peak) (r(s)=-0.68, p=0.014) and VO2peak (r(s)=-0.60, p=0.039) with HIT but not with AET. In conclusion, pre-training cardiac sympathovagal balance and its initial alterations in response to acute HIT exercise were related to fitness responses to short-term HIT.