The gut microbiome is involved in nutrient metabolism and produces metabolites that, via the gut–brain axis, signal to the brain and influence cognition. Human studies have so far had limited success in identifying early metabolic alterations linked to cognitive aging, likely due to limitations in metabolite coverage or follow-ups. Older persons from the Three-City population-based cohort who had not been diagnosed with dementia at the time of blood sampling were included, and repeated measures of cognition over 12 subsequent years were collected. Using a targeted metabolomics platform, we identified 72 circulating gut-derived metabolites in a case–control study on cognitive decline, nested within the cohort (discovery n = 418; validation n = 420). Higher serum levels of propionic acid, a short-chain fatty acid, were associated with increased odds of cognitive decline (OR for 1 SD = 1.40 (95% CI 1.11, 1.75) for discovery and 1.26 (1.02, 1.55) for validation). Additional analyses suggested mediation by hypercholesterolemia and diabetes. Propionic acid strongly correlated with blood glucose (r = 0.79) and with intakes of meat and cheese (r > 0.15), but not fiber (r = 0.04), suggesting a minor role of prebiotic foods per se, but a possible link to processed foods, in which propionic acid is a common preservative. The adverse impact of propionic acid on metabolism and cognition deserves further investigation.