Homeostasis of the gut microbiota critically influences host health and aging. Developing genetically engineered probiotics holds great promise as a new therapeutic paradigm to promote healthy aging. Here, through screening 3,983 Escherichia coli mutants, we discovered that 29 bacterial genes, when deleted, increase longevity in the host Caenorhabditis elegans. A dozen of these bacterial mutants also protect the host from age-related progression of tumor growth and amyloid-beta accumulation. Mechanistically, we discovered that five bacterial mutants promote longevity through increased secretion of the polysaccharide colanic acid (CA), which regulates mitochondrial dynamics and unfolded protein response (UPRmt) in the host. Purified CA polymers are sufficient to promote longevity via ATFS-1, the host UPRmt-responsive transcription factor. Furthermore, the mitochondrial changes and longevity effects induced by CA are conserved across different species. Together, our results identified molecular targets for developing pro-longevity microbes and a bacterial metabolite acting on host mitochondria to promote longevity.