Oncolytic virotherapy has currently emerged as a promising approach upon which scientists have been able to induce tumor-specific cell death in a broad spectrum of malignancies. Paramyxoviruses represent intrinsic oncolytic capability, which makes them excellent candidates to be widely used in oncolytic virotherapy. The mechanisms through which these viruses destroy the cancerous cells involve triggering the autophagic machinery and apoptosis in target cells. Interestingly, oncolytic paramyxoviruses have been found to induce autophagy and lead to tumor cells death rather than their survival. Indeed, the induction of autophagy has been revealed to enhance the immunogenicity of tumor cells via the release of damage-associated molecular patterns (DAMPs) and the activation of autophagy-related immunogenic cell death (ICD). Subsequent cross-presentation of tumor-associated antigens (TAA) through the MHC-I complex to CD8+ T cells results in the productive priming of the tumor-specific immune response. In this review, we first briefly discuss autophagy and explain the process of viral xenophagy. Finally, we focus on the interactions between virus and autophagy proteins, elaborating on the global preclinical studies on oncolytic paramyxoviruses.