Patients with advanced solid tumors frequently relapse and succumb to their metastatic disease after developing resistance to conventional treatment modalities such as chemotherapy and radiotherapy. In these patients, novel strategies of targeting widespread tumors are urgently needed. The increasing knowledge of the underlying pathogenetic mechanisms has led to the identification of numerous molecules that are overexpressed in various tumors and accumulate at the cell surface. The use of genetically modified bacteria and their toxins targeting these surface molecules has emerged as a promising new treatment strategy in refractory cancers. This review focuses on bacterial toxins such as Diphtheria toxin (DT), Pseudomonas exotoxin A (PE) and Clostridium perfringens enterotoxin (CPE). In addition, the use of anaerobic bacteria such as Clostridium, Salmonella and Bifidobacterium spp. as drug-delivery systems targeting hypoxic tumor areas will be discussed as a new therapeutic modality of advanced solid tumors.