Interactions with the microbiota influence many aspects of immunity, including immune cell development, differentiation, and function. Here, we examined the impact of the microbiota on CD8+ T cell memory. Antigen-activated CD8+ T cells transferred into germ-free mice failed to transition into long-lived memory cells and had transcriptional impairments in core genes associated with oxidative metabolism. The microbiota-derived short-chain fatty acid (SCFA) butyrate promoted cellular metabolism, enhanced memory potential of activated CD8+ T cells, and SCFAs were required for optimal recall responses upon antigen re-encounter. Mechanistic experiments revealed that butyrate uncoupled the tricarboxylic acid cycle from glycolytic input in CD8+ T cells, which allowed preferential fueling of oxidative phosphorylation through sustained glutamine utilization and fatty acid catabolism. Our findings reveal a role for the microbiota in promoting CD8+ T cell long-term survival as memory cells and suggest that microbial metabolites guide the metabolic rewiring of activated CD8+ T cells to enable this transition.