Previous studies have suggested beneficial effects of physical activity on cognition. Here, we asked in an interventional approach if physical activity performed at different intensity levels would differentially affect episodic memory function. Additionally, we tried to identify mechanisms mediating these changes. Sixty-two healthy elderly individuals were assessed for level of physical activity, aerobic fitness, episodic memory score, neurotrophin and catecholamine levels, and received a magnetic resonance image of the brain at baseline and after a six months intervention of medium or low-intensity physical activity or control. Increase in total physical activity was positively associated with increase in memory score over the entire cohort, without significant differences between intensity groups. It was also positively associated with increases in local gray matter volume in prefrontal and cingulate cortex, and BDNF levels (trend). In conclusion, we showed that physical activity conveys the beneficial effects on memory function independently of its intensity, possibly mediated by local gray matter volume and neurotrophic factors. Our findings may carry significant implications for prevention of cognitive decline in the elderly.