Since the nineteenth century, several reports in the historical medical literature emphasized that, occasionally, cancer patients showed a clinical remission, called "Saint Peregrine tumor" as a result of natural infections. Moreover, additional evidence indicated that viruses show a tropism toward cancer cells, leading to the discovery of oncolytic activity of several viruses, called oncolytic viruses (OVs). With the technological and scientific advancements, the advent of rodent models, the establishment of in vitro cell lines, the introduction of methods for virus propagation, several attempts through the 1950s and 1970s have been made to increase OVs specificity, efficacy and safety; however, inconclusive/negative results have been reached and many researchers abandoned the field. Only in the later 1990s, the genetic engineering and the recombinant DNA techniques that allowed the generation of potent, specific and safe OVs and a better understanding of cancer cells renewed the interest in virotherapy. Currently, virotherapy represents a cancer therapeutic strategy based on the use of OVs that selectively infect and lyse cancer cells, without harming normal cells. Over the past years, several "natural" and "genetic engineered" viruses, have been investigated in clinical studies and some of them revealed encouraging results. Recently, the clinical use of OVs has also been supported by the immune stimulatory property of OVs against tumor cells. Here, we analyze the early oncolytic virotherapy before genetic engineering to highlight the relevant progresses reached, and the mechanism to stimulate host immune response, a significant challenge in current virotherapy field.