Cancer has become the second ranking cause of death in the industrialized world. Conventional anti-cancer therapies such as surgery, radiotherapy, and chemotherapy are effective in the treatment of solid tumors only to some extent. Furthermore, they are often associated with severe side effects. Use of bacteria as alternative cancer therapeutics has sporadically been followed over more than a century. The potential to target and colonize solid tumors could be shown for many different bacteria in the meantime. Such bacteria are either obligate anaerobic bacteria like Clostridium or Bifidobacterium or facultative anaerobic like Escherichia coli or Salmonella. Here we describe bacterial strains that were successfully applied mostly in animals bearing model tumors, although first clinical trials have been reported as well. Our review mainly concentrates on Salmonella enterica serovar Typhimurium (S. Typhimurium) since these bacteria were studied most intensively thus far. Importantly, S. Typhimurium were shown not only to colonize large established tumors but also exhibit the property to invade and affect metastases. We report on a potential mechanism by which such bacteria can invade solid tumors. Furthermore, we describe several successful attempts in which the bacteria have been used as carriers for recombinant therapeutic molecules that render bacteria more powerful in eradication of the established tumor. Such attempts should be considered starting points on the way to an effective and safe tumor therapy with the help of bacteria.