Interactions with the microbiota influence many aspects of immunity, including immune cell development, differentiation and function. Here we examined the impact of microbiota on one of the key functions of CD8+ T cells, the transition to long-lived and protective memory. Antigen-activated CD8+ T cells transferred into germ-free mice failed to transition into long-lived memory cells with enhanced recall capacity and had transcriptional impairments in oxidative metabolism. To the contrary, the microbiota-derived short-chain fatty acid (SCFA) butyrate promoted cellular metabolism, enhanced memory potential of activated CD8+ T cells and was required for optimal recall responses upon antigen re-encounter. Mechanistic experiments revealed that the SCFA butyrate increased turnover of glycolysis and oxidative phosphorylation (OXPHOS) of effector CD8+ T cells but led to a partial uncoupling of the tricarboxylic acid cycle from glycolytic input. This allowed preferential fueling of oxidative phosphorylation through short-chain fatty acids. Our findings reveal a role for the microbiota in promoting CD8+ T cell long-term survival as memory cells and suggest that microbial metabolites potentially guide the metabolic rewiring of activated CD8+ T cells that enables this transition.