This study explored the autonomic nervous system (ANS) adaptation in relation to exercise and how this correlates with the ratings of perceived exertion (Borg-RPE) over four ranges 6-8; 9-12; 13-16; 17-20, by using the time domain parameters and the multi-lag Tone-Entropy (T-E) of heart rate variability (HRV). ECG signals were collected from ten subjects who were recruited to participate in a graded exercise protocol on a treadmill. Results showed that SDNN and RMSSD decreased from lower to higher Borg-RPE, indicating a decrease in HRV. Entropy significantly decreased along the first 3 Borg-RPE ranges but increased in the recovery phase in which Tone values became negative (high HRV). As Borg-RPE values increased to the 17-20 range, Tone values decreased and Entropy increased compared to the 13-16 interval suggesting vagal predominance as opposed to HRV time domain results. The highest value of Tone was observed in the Borg-RPE 9-12 range indicating paramount sympathetic dominance. The use of multi-lag in T-E 2D space improved the separation of HRV with reference to the Borg-RPE intervals (p<0.05), except between the 13-16 and 17-20 ranges of the Borg-RPE. Results highlighted the analytical power of T-E in assessing both HRV changes and the sympatho-vagal balance throughout a graded exercise. Potentially, T-E analysis can be applied to assess rehabilitation settings and to get further information on ANS modulation at high exercise intensities.