A progressive loss of protein homeostasis is characteristic of aging and a driver of neurodegeneration. To investigate this process quantitatively, we characterized proteome dynamics during brain aging in the short-lived vertebrate Nothobranchius furzeri combining transcriptomics and proteomics. We detected a progressive reduction in the correlation between protein and mRNA, mainly due to post-transcriptional mechanisms that account for over 40% of the age-regulated proteins. These changes cause a progressive loss of stoichiometry in several protein complexes, including ribosomes, which show impaired assembly/disassembly and are enriched in protein aggregates in old brains. Mechanistically, we show that reduction of proteasome activity is an early event during brain aging and is sufficient to induce proteomic signatures of aging and loss of stoichiometry in vivo. Using longitudinal transcriptomic data, we show that the magnitude of early life decline in proteasome levels is a major risk factor for mortality. Our work defines causative events in the aging process that can be targeted to prevent loss of protein homeostasis and delay the onset of age-related neurodegeneration.