The aim of this study was to analyze the recovery of heart rate variability (HRV) after treadmill exercise and to investigate the autonomic nervous system response after exercise. Frequency domain indices, i.e., LF(ms(2)), HF(ms(2)), LF(n.u.), HF(n.u.) and LF/HF, and lagged Poincare plot width (SD1 (m) ) and length (SD2 (m) ) were introduced for comparison between the baseline period (Pre-E) before treadmill running and two periods after treadmill running (Post-E1 and Post-E2). The correlations between lagged Poincare plot indices and frequency domain indices were applied to reveal the long-range correlation between linear and nonlinear indices during the recovery of HRV. The results suggested entirely attenuated autonomic nervous activity to the heart following the treadmill exercise. After the treadmill running, the sympathetic nerves achieved dominance and the parasympathetic activity was suppressed, which lasted for more than 4 min. The correlation coefficients between lagged Poincare plot indices and spectral power indices could separate not only Pre-E and two sessions after the treadmill running, but also the two sessions in recovery periods, i.e., Post-E1 and Post-E2. Lagged Poincare plot as an innovative nonlinear method showed a better performance over linear frequency domain analysis and conventional nonlinear Poincare plot.