Bacterial-based tumor-targeted therapy is an area of growing interest and holds promise for the treatment of solid tumors. Upon systemic administration, various types of non-pathogenic obligate anaerobes and facultative anaerobes have been shown to infiltrate and selectively replicate within solid tumors. The tumor specificity is based upon the unique physiology of solid tumors, which is often characterized by regions of hypoxia and necrosis. Prokaryotic vectors can be safely administered and their potential to deliver therapeutic proteins has been demonstrated in a variety of preclinical models. Although the amount of clinical experience with bacterial vectors is limited to date, the available data clearly demonstrated the feasibility of bacterial-mediated therapy in humans. There are several issues however that are still unknown and remain major challenges. In this review, using Clostridium and modified Salmonella as prototypical agents, we will discuss the major advantages, challenges and shortcomings of bacterial systems for tumor-specific therapy. In addition, we will highlight the requirements needed to advance the approach into clinical trials.