The Encoding-Specificity Paradigm indicates that memory recall will be superior when contextual factors are congruent between memory encoding and memory retrieval. However, unlike other contextual conditions (e.g., verbal context, mental operations, global feature context, mood dependency, and physical operations), this paradigm has nearly been ignored in the exercise domain. Thus, the purpose of this study was to examine the Encoding-Specificity Paradigm in the context of exercise and rest conditions. 24 young adults (age: M = 21 years) completed a within-subject, counterbalanced experiment involving four laboratory visits, including 1) R-R (rest-rest) condition, 2) R-E (rest-exercise) condition, 3) E-R (exercise-rest) condition, or 4) E-E (exercise-exercise) condition. The exercise bout included a 15-minute moderate-intensity walk on a treadmill. Memory recall was assessed via a 15 word-list task. Memory recall was greater for R-R (8.71 ± 3.1) versus R-E (7.46 ± 2.8), and similarly, for E-E (8.63 ± 2.7) versus E-R (8.21 ± 2.7). The mean word recall for the congruent and incongruent conditions, respectively, was 8.67 (2.4) and 7.83 (2.4). There was a statistically significant condition effect (F = 5.02; P = .03; partial η² = .18). This experiment provides direct support for the Encoding-Specificity Paradigm in the exercise domain.