Conventional cancer chemotherapies are not fully efficacious and do not target tumors, leading to significant treatment-related morbidities. A number of genetically attenuated cancer-targeting bacteria are being developed to safely target tumors in vivo. Here we report the toxicological, tumor-targeting, and efficacy profiles of Salmonella enterica serovar Typhimurium CRC2631 in a syngeneic and autochthonous TRAMP model of aggressive prostate cancer. CRC2631 preferentially colonize primary and metastatic tumors in the TRAMP animals. In addition, longitudinal whole genome sequencing studies of CRC2631 recovered from prostate tumor tissues demonstrate that CRC2631 is genetically stable. Moreover, tumor-targeted CRC2631 generates an anti-tumor immune response. Combination of CRC2631 with checkpoint blockade reduces metastasis burden. Collectively, these findings demonstrate a potential for CRC2631 in cancer immunotherapy strategies.