Stress-related memory deficit is correlated with dendritic spine loss. Physical exercise improves memory function and promotes spinogenesis. However, no studies have been performed to directly observe exercise-related effects on spine dynamics, in association with memory function. This study utilized transcranial two-photon in vivo microscopy to investigate dendritic spine formation and elimination in barrel cortex of mice under physical constrain or naive conditions, followed by memory performance in a whisker-dependent novel texture discrimination task. We found that stressed mice had elevated spine elimination rate in mouse barrel cortex plus deficits in memory retrieval, both of which can be rescued by chronic exercise on treadmill. Exercise also elevated brain-derived neurotrophic factor (BDNF) expression in barrel cortex. The above-mentioned rescuing effects for both spinognesis and memory function were abolished after inhibiting BDNF/tyrosine kinase B (TrkB) pathway. In summary, this study demonstrated the improvement of stress-associated memory function by exercise via facilitating spine retention in a BDNF/TrkB-dependent manner.