The rhabdovirus Maraba has recently been characterized as a potent oncolytic virus. In the present study, we engineered an attenuated Maraba strain, defined as MG1, to express a melanoma-associated tumor antigen. Its ability to mount an antitumor immunity was evaluated in tumor-free and melanoma tumor-bearing mice. Alone, the MG1 vaccine appeared insufficient to prime detectable adaptive immunity against the tumor antigen. However, when used as a boosting vector in a heterologous prime-boost regimen, MG1 vaccine rapidly generated strong antigen-specific T-cell immune responses. Once applied for treating syngeneic murine melanoma tumors, our oncolytic prime-boost vaccination protocol involving Maraba MG1 dramatically extended median survival and allowed complete remission in more than 20% of the animals treated. This work describes Maraba virus MG1 as a potent vaccine vector for cancer immunotherapy displaying both oncolytic activity and a remarkable ability to boost adaptive antitumor immunity.