Mutations in the gene encoding the microtubule-severing protein spastin (spastic paraplegia 4 [SPG4]) cause hereditary spastic paraplegia (HSP), associated with neurodegeneration, spasticity, and motor impairment. Complicated forms (complicated HSP [cHSP]) further include cognitive deficits and dementia; however, the etiology and dysfunctional mechanisms of cHSP have remained unknown. Here, we report specific working and associative memory deficits upon spastin depletion in mice. Loss of spastin-mediated severing leads to reduced synapse numbers, accompanied by lower miniature excitatory postsynaptic current (mEPSC) frequencies. At the subcellular level, mutant neurons are characterized by longer microtubules with increased tubulin polyglutamylation levels. Notably, these conditions reduce kinesin-microtubule binding, impair the processivity of kinesin family protein (KIF) 5, and reduce the delivery of presynaptic vesicles and postsynaptic α-amino-3-hydroxy-5-methyl-4-isoxazolepropionic acid (AMPA) receptors. Rescue experiments confirm the specificity of these results by showing that wild-type spastin, but not the severing-deficient and disease-associated K388R mutant, normalizes the effects at the synaptic, microtubule, and transport levels. In addition, short hairpin RNA (shRNA)-mediated reduction of tubulin polyglutamylation on spastin knockout background normalizes KIF5 transport deficits and attenuates the loss of excitatory synapses. Our data provide a mechanism that connects spastin dysfunction with the regulation of kinesin-mediated cargo transport, synapse integrity, and cognition.