Changes in the stability of microtubules regulate many biological processes, but their role in memory remains unclear. Here we show that learning causes biphasic changes in the microtubule-associated network in the hippocampus. In the early phase, stathmin is dephosphorylated, enhancing its microtubule-destabilizing activity by promoting stathmin-tubulin binding, whereas in the late phase these processes are reversed leading to an increase in microtubule/KIF5-mediated localization of the GluA2 subunit of AMPA receptors at synaptic sites. A microtubule stabilizer paclitaxel decreases or increases memory when applied at the early or late phases, respectively. Stathmin mutations disrupt changes in microtubule stability, GluA2 localization, synaptic plasticity and memory. Aged wild-type mice show impairments in stathmin levels, changes in microtubule stability and GluA2 localization. Blocking GluA2 endocytosis rescues memory deficits in stathmin mutant and aged wild-type mice. These findings demonstrate a role for microtubules in memory in young adult and aged individuals.