Throughout history, psychologists and philosophers have proposed that good sleep benefits memory, yet current studies focusing on the relationship between traditionally reported sleep features (e.g., minutes in sleep stages) and changes in memory performance show contradictory findings. This discrepancy suggests that there are events occurring during sleep that have not yet been considered. The autonomic nervous system (ANS) shows strong variation across sleep stages. Also, increases in ANS activity during waking, as measured by heart rate variability (HRV), have been correlated with memory improvement. However, the role of ANS in sleep-dependent memory consolidation has never been examined. Here, we examined whether changes in cardiac ANS activity (HRV) during a daytime nap were related to performance on two memory conditions (Primed and Repeated) and a nonmemory control condition on the Remote Associates Test. In line with prior studies, we found sleep-dependent improvement in the Primed condition compared with the Quiet Wake control condition. Using regression analyses, we compared the proportion of variance in performance associated with traditionally reported sleep features (model 1) vs. sleep features and HRV during sleep (model 2). For both the Primed and Repeated conditions, model 2 (sleep + HRV) predicted performance significantly better (73% and 58% of variance explained, respectively) compared with model 1 (sleep only, 46% and 26% of variance explained, respectively). These findings present the first evidence, to our knowledge, that ANS activity may be one potential mechanism driving sleep-dependent plasticity.