Memory impairment is common in persons with epilepsy (PWE), and exercise may be a strategy for its improvement. In this pilot study, we hypothesized that exercise rehabilitation would improve physical fitness and verbal memory and induce changes in brain networks involved in memory processes. We examined the effects of combined endurance and resistance exercise rehabilitation on memory and resting state functional connectivity (rsFC). Participants were randomized to exercise (PWE-E)or control (PWE-noE). The exercise intervention consisted of 18 supervised sessions on nonconsecutive days over 6 weeks. Before and after the intervention period, both groups completed self-report assessments (Short Form-36 (SF-36), Baecke Questionnaire (BQ)of habitual physical activity, and Profile of Mood States (POMS)), cognitive testing (California Verbal Learning Test-II (CVLT-II)), and magnetic resonance imaging (MRI); PWE-E also completed exercise performance tests. After completing the study, PWE-noE were offered cross-over to the exercise arm. There were no differences in baseline demographic, clinical, or assessment variables between 8 PWE-noE and 9 PWE-E. Persons with epilepsy that participated in exercise intervention increased maximum voluntary strength (all strength tests p < 0.05)and exhibited nonsignificant improvement in cardiorespiratory fitness (p = 0.15). Groups did not show significant changes in quality of life (QOL)or habitual physical activity between visits. However, there was an effect of visit on POMS total mood disturbance (TMD)measure showing improvement from baseline to visit 2 (p = 0.023). There were significant group by visit interactions on CVLT-II learning score (p = 0.044)and total recognition discriminability (d′)(p = 0.007). Persons with epilepsy that participated in exercise intervention had significant reductions in paracingulate rsFC with the anterior cingulate and increases in rsFC for the cerebellum, thalamus, posterior cingulate cortex (PCC), and left and right inferior parietal lobule (IPL)(corrected p < 0.05). Change in CVLT-II learning score was associated with rsFC changes for the paracingulate cortex (rS = − 0.67; p = 0.0033), left IPL (rS = 0.70; p = 0.0019), and right IPL (rS = 0.71; p = 0.0015)while change in d′ was associated with change in cerebellum rsFC to angular/middle occipital gyrus (rS = 0.68; p = 0.0025). Our conclusion is that exercise rehabilitation may facilitate verbal memory improvement and brain network functional connectivity changes in PWE and that improved memory performance is associated with changes in rsFC. A larger randomized controlled trial of exercise rehabilitation for cognitive improvement in PWE is warranted.