Bacteria actively secrete extracellular vesicles (EVs), spherical nano-sized proteolipids into the extracellular milieu. Bacterial EVs have gained wide interests as non-living complex vaccines or delivery vehicles. However, no studies have used bacterial EVs in treating cancer so far. Our results showed remarkable capability of EVs derived from Escherichia coli W3110 msbB-deficient mutant to effectively induce long-term anti-tumor immune responses that can fully eradicate established tumors without notable adverse effects. This anti-tumor effect was IFN-γ-dependent, and we present a comprehensive proteome of E. coli W3110 msbB-deficient EVs to investigate which vesicular components induce the anti-tumor effects.