Although aging is known to impair intermediate-term memory in Drosophila, its effect on protein-synthesis-dependent long-term memory (LTM) is unknown. We show here that LTM is impaired with age, not due to functional defects in synaptic output of mushroom body (MB) neurons, but due to connectivity defects of dorsal paired medial (DPM) neurons with their postsynaptic MB neurons. GFP reconstitution across synaptic partners (GRASP) experiments revealed structural connectivity defects in aged animals of DPM neurons with MB axons in the α lobe neuropil. As a consequence, a protein-synthesis-dependent LTM trace in the α/β MB neurons fails to form. Aging thus impairs protein-synthesis-dependent LTM along with the α/β MB neuron LTM trace by lessening the connectivity of DPM and α/β MB neurons.