Age-related cognitive decline is a serious health concern in our aging society. Decreased cognitive function observed during healthy brain aging is most likely caused by changes in brain connectivity and synaptic dysfunction in particular brain regions. Here we show that aged C57BL/6J wildtype mice have hippocampus-dependent spatial memory impairments. To identify the molecular mechanisms that are relevant to these memory deficits we investigated the temporal profile of mouse hippocampal synaptic proteome changes at 20, 40, 50, 60, 70, 80, 90 and 100 weeks of age. Extracellular matrix proteins were the only group of proteins that showed a robust and progressive upregulation over time. This was confirmed by immunoblotting and histochemical analysis, indicating that the increased levels of hippocampal extracellular matrix may limit synaptic plasticity as a potential cause of age-related cognitive decline. In addition, we observed that stochasticity in synaptic protein expression increased with age, in particular for proteins that were previously linked with various neurodegenerative diseases, whereas low variance in expression was observed for proteins that play a basal role in neuronal function and synaptic neurotransmission. Together, our findings show that both specific changes and increased variance in synaptic protein expression are associated with aging and may underlie reduced synaptic plasticity and impaired cognitive performance at old age.