More than a century ago, independent groups raised the possibility of using bacteria to selectively infect tumours. Such treatment induces an immune reaction that can cause tumour rejection and protect the patient against further recurrences. One of the first holistic approximations to use bacteria in cancer treatment was performed by William Coley, considered the father of immune-therapy, at the end of XIX century. Since then, many groups have used different bacteria to test their antitumour activity in animal models and patients. The basis for this reactivity implies that innate immune responses activated upon bacteria recognition, also react against the tumour. Different publications have addressed several aspects of oncolytic bacteria. In the present review, we will focus on revisiting the historical aspects using bacteria as oncolytic agents and how they led to the current clinical trials. In addition, we address the molecules present in oncolytic bacteria that induce specific toxic effects against the tumors as well as the activation of host immune responses in order to trigger antitumour immunity. Finally, we discuss future perspectives that could be considered in the different fields implicated in the implementation of this kind of therapy in order to improve the current use of bacteria as oncolytic agents.