We will revisit the dual role of the immune system in controlling and enabling tumor progression, known as cancer immunoediting. We will go through the different phases of this phenomenon, exposing the most relevant evidences obtained from experimental models and human clinical data, with special focus on Cutaneous Melanoma, an immunogenic tumor per excellence. We will describe the different immunotherapeutic strategies employed and consider current models accounting for tumor heterogeneity. And finally, we will propose a rational discussion of the progress made and the future challenges in the therapeutics of Cutaneous Melanoma, taking into consideration that tumor evolution is the resulting from a continuous feedback between tumor cells and their environment, and that different combinatorial therapeutic approaches can be implemented according to the tumor stage.