Heart Rate Recovery (HRR) after exercise is commonly used as a marker of physical condition. Although a number of studies have addressed the clinical usefulness of Heart Rate Variability (HRV) as a marker of the autonomic activity, few works have studied the complex physiological responses during and after high intensity exercise by means of HRV nonlinear dynamics. In this study, we selected a set of nonlinear indices, measuring different aspects of the underlying physiological mechanisms, in order to assess the HRV evolution in an All Out Exercise Test in eight male amateur triathletes. Namely, Sample Entropy (Sam-pEn), and α1 and α2 from Detrended Fluctuation Analysis were chosen. We additionally proposed a measure to quantify HRV Recovery (HRVR) after exercising for any index. Our results showed that: (1) SampEn decreased drastically during exercise and it slightly recovered within 5 minutes of rest; (2) α1 decreased during exercise, but its values were reestablished immediately after; (3) Oppositely, α2 increased during exercise, following a slight recovery of its values in the rest time. No correlation was found between HRR and HRVR. The performance of nonlinear HRV indices after high intensity exercise suggest relevant information underlying physiological recovery that can be used to assess physical condition or cardiovascular risk.