Melanoma is the deadliest type of skin cancer with steadily increasing incidence worldwide during the last few decades. In addition to its tumor associated antigens (TAAs), melanoma has a high mutation rate compared to other tumors, which promotes the appearance of tumor specific antigens (TSAs) as well as increased lymphocytic infiltration, inviting the use of therapeutic tools that evoke new or restore pre-existing immune responses. Innovative therapeutic proposals, such as immune checkpoint inhibitors (ICIs), have emerged as effective options for melanoma. However, a significant portion of these patients relapse and become refractory to treatment. Likewise, strategies using viral vectors, replicative or not, have garnered confidence and approval by different regulatory agencies around the world. It is possible that further success of immune therapies against melanoma will come from synergistic combinations of different approaches. In this review we outline molecular features inherent to melanoma and how this supports the use of viral oncolysis and immunotherapies when used as monotherapies or in combination.