Recent evidence suggests that the autonomic nervous system can contribute to memory consolidation during sleep. Whether fluctuations in cardiac autonomic activity during sleep following physical exercise contribute to the process of memory consolidation has not been studied. We assessed the effects of a non-rapid eye movement (NREM) nap following acute exercise on cardiac autonomic regulation assessed with heart rate variability (HRV) to examine if HRV influences memory processes. Fifty-six (59% female) healthy young adults (23.14 ± 3.74 years) were randomly allocated to either the exercise plus nap (ExNap, n = 27) or nap alone (NoExNap, n = 29) groups. The ExNap group performed a 40-minute moderate-intensity cycling, while the NoExNap group was sedentary prior to learning 45 neutral pictures for a later test. Subsequently, participants underwent a 60-minute NREM nap while measuring EKG, followed by a visual recognition test. Our results indicated that heart rate did not significantly differ between the groups (p = 0.302); whereas vagally-mediated HRV indices were lower in the ExNap group compared to the NoExNap group (p < 0.05). There were no significant differences in sleep variables (p > 0.05). Recognition accuracy was significantly higher in the ExNap group than in the NoExNap group (p = 0.027). In addition, the recognition accuracy of the ExNap group was negatively associated with vagally-mediated HRV (p < 0.05). Pre-nap acute exercise attenuated parasympathetic activity and appears to alter the relationship between memory and cardiac autonomic activity, suggesting that post-exercise memory enhancement may be based on other mechanisms.