This work investigated the suitability of a new tool for decision support in training programs of high performance athletes. The aim of this study was to find a reliable and robust measure of the fitness of an athlete for use as a tool for adjusting training schedules. We examined the use of heart rate recovery percentage (HRr%) for this purpose, using a two-phased approach. Phase 1 consisted of testing the suitability of HRr% as a measure of aerobic fitness, using a modified running test specifically designed for high-performance team running sports such as football. Phase 2 was conducted over a 12-week training program with two different training loads. HRr% measured aerobic fitness and a running time-trial measured performance. Consecutive measures of HRr% during phase 1 indicated a Pearson’s r of 0.92, suggesting a robust measure of aerobic fitness. During phase 2, HRr% reflected the training load and significantly increased when the training load was reduced between weeks 4 to 5. This work shows that HRr% is a robust indicator of aerobic fitness and provides an on-the-spot index that is useful for training load adjustment of elite-performance athletes.