Major individual differences in the maximal oxygen uptake response to aerobic training have been documented. Vagal influence on the heart has been shown to contribute to changes in aerobic fitness. Whether vagal influence on the heart also predicts maximal oxygen uptake response to interval-sprinting training, however, is undetermined. Thus, the relationship between baseline vagal activity and the maximal oxygen uptake response to interval-sprinting training was examined. Exercisers (n = 16) exercised three times a week for 12 weeks, whereas controls did no exercise (n = 16). Interval-sprinting consisted of 20 min of intermittent sprinting on a cycle ergometer (8 s sprint, 12 s recovery). Maximal oxygen uptake was assessed using open-circuit spirometry. Vagal influence was assessed through frequency analysis of heart rate variability. Participants were aged 22 ± 4.5 years and had a body mass of 72.7 ± 18.9 kg, a body mass index of 26.9 ± 3.9 kg · m(-2), and a maximal oxygen uptake of 28 ± 7.4 ml · kg(-1) · min(-1). Overall increase in maximal oxygen uptake after the training programme, despite being anaerobic in nature, was 19 ± 1.2%. Change in maximal oxygen uptake was correlated with initial baseline heart rate variability high-frequency power in normalised units (r = 0.58; P < 0.05). Thus, cardiac vagal modulation of heart rate was associated with the aerobic training response after 12 weeks of high-intensity intermittent-exercise. The mechanisms underlying the relationship between the aerobic training response and resting heart rate variability need to be established before practical implications can be identified.