The concept of using replicating oncolytic viruses in cancer therapy dates to the beginning of the twentieth century. However, in the last few years, an increasing number of pre-clinical and clinical trials have been carried out with promising preliminarily results. Novel, indeed, is the suggestion that viral oncolytic therapy might not operate exclusively through an oncolysis-mediated process but additionally requires the “assistance” of the host’s immune system. Originally, the host’s immune response was believed to play a predominant obstructive role against viral replication, hence limiting the anti-tumor efficacy of viral vectors. Recent data, however, suggest that the immune response may also play a key role in promoting tumor destruction in association with the oncolytic process. In fact, immune effector pathways activated during oncolytic virus-induced tumor rejection seem to follow a similar pattern to those observed when the broader phenomenon of immune-mediated tissue-specific rejection occurs in other immune-related pathologies. We recently formulated the “Immunologic Constant of Rejection” hypothesis, emphasizing commonalties in transcriptional patterns observed when tissue-destruction occurs: whether with a favorable outcome, such as in tumor rejection and pathogen clearance; or a destructive one, such as in allograft rejection or autoimmunity. Here, we propose that a similar mechanism induces clearance of virally infected tumors and that such a mechanism is primarily dependent on innate immune functions.