A growing body of evidence supports the notion that the gut microbiome plays an important role in cancer immunity. However, the underpinning mechanisms remain to be fully elucidated. One attractive hypothesis envisages that among the T cells elicited by the plethora of microbiome proteins a few exist that incidentally recognize neo-epitopes arising from cancer mutations (“molecular mimicry (MM)” hypothesis). To support MM, the human probiotic Escherichia coli Nissle was engineered with the SIINFEKL epitope (OVA-E.coli Nissle) and orally administered to C57BL/6 mice. The treatment with OVA-E.coli Nissle, but not with wild type E. coli Nissle, induced OVA-specific CD8⁺ T cells and inhibited the growth of tumors in mice challenged with B16F10 melanoma cells expressing OVA. The microbiome shotgun sequencing and the sequencing of TCRs from T cells recovered from both lamina propria and tumors provide evidence that the main mechanism of tumor inhibition is mediated by the elicitation at the intestinal site of cross-reacting T cells, which subsequently reach the tumor environment. Importantly, the administration of Outer Membrane Vesicles (OMVs) from engineered E. coli Nissle, as well as from E. coli BL21(DE3)ΔompA, carrying cancer-specific T cell epitopes also elicited epitope-specific T cells in the intestine and inhibited tumor growth. Overall, our data strengthen the important role of MM in tumor immunity and assign a novel function of OMVs in host-pathogen interaction. Moreover, our results pave the way to the exploitation of probiotics and OMVs engineered with tumor specific-antigens as personalized mucosal cancer vaccines.