A major obstacle for the development of effective immunotherapy is the ability of tumors to escape the immune system. The possibility to kill tumor cells because they are recognized as infected rather than as malignant could help overcome immune escape mechanisms. Here we report a conceptually new approach of cancer immunotherapy based on in vivo infection of tumors and killing of infected tumor cells. Attenuated but still invasive, Salmonella typhimurium can be successfully exploited to invade melanoma cells that can present antigenic determinants of bacterial origin and become targets for anti-Salmonella–specific T cells. However, to fully appreciate the anticancer therapeutic properties of S. typhimurium, tumor-bearing mice need to be vaccinated against S. typhimurium before intratumoral Salmonella injection. Tumor infection when coupled to anti-Salmonella vaccination leads to 50% to 100% tumor-free mice with a better outcome on larger tumors. Invasive Salmonella also exert an indirect toxic effect on tumor cells through the recruitment of inflammatory cells and the cross-presentation of tumor antigens, which allow induction of tumor-specific immune response. This is effective in retarding the growth of untreated established distant tumors and in protecting the mice from subsequent tumor challenges.