Heart rate variability (HRV) is a simple and noninvasive measure that estimates cardiac autonomic modulation, mainly the parasympathetic contribution. Increased sympathetic and/or decreased parasympathetic nervous activity is seen in post-myocardial infarction (MI) patients. Consequently, these patients present reduced HRV, which has been associated with increased risk of adverse events and mortality. Exercise training, recommended as a complementary therapy for patients with cardiovascular disease, has shown numerous beneficial effects. The main aim of the present manuscript was to provide a critical review of studies investigating the effects of exercise training on cardiac autonomic modulation, through HRV, in MI patients and the possible mechanisms involved. Despite conflicting evidence, exercise training appears to be a useful therapeutic intervention to improve the unbalanced autonomic function of MI patients. Finally, the mechanisms involved are not yet well understood, but nitric oxide bioavailability and angiotensin II levels seem to play an important role.