We aimed to analyse the complexity and fractal nature of heartbeat during constant exercise, at three different intensities, and recovery. Fourteen healthy men underwent 4 separate sessions. The first session was an incremental treadmill test to determine ventilatory thresholds (VT1 and VT2) and maximal aerobic speed (MAS). Each subject ran at VT1 and VT2 speeds and MAS (second, third and fourth day). The duration of VT1 and VT2 loads were selected in such a way that the product intensity-duration (training load) was the same. Sample Entropy (SampEn) and slope of Detrended Fluctuation Analysis (DFA α1) were measured during the whole session. DFA α1 declines with exercise, being less in the VT1 trial than in the other two. SampEn shows no significant change during exercise. The three tests induce the same decline in SampEn, but at the highest intensity (MAS) tends to decline during the exercise itself, whereas at lower intensities (VT1, VT2) the decline is delayed (10 min of recovery). Subsequently, SampEn at VT1 gradually recovers, whereas at VT2 and MAS it remains stable during recovery. In conclusion, exercise produces a loss of heartbeat complexity, but not fractal nature, during recovery and it depends on intensity.