Melanoma is the deadliest form of skin cancer. Cutaneous melanomas usually originate from exposure to the mutagenic effects of ultraviolet radiation, and as such they exhibit the highest rate of somatic mutations than any other human cancer, and an extensive expression of neoantigens concurrently with a dense infiltrate of immune cells. The coexistence of high immunogenicity and high immune cell infiltration may sound contradictory for cancers carrying a gloomy outcome. However, recent studies have unveiled a variety of immunosuppressive mechanisms that often permeate the tumor microenvironment and that are responsible for tumor escaping from immunosurveillance mechanisms. Nonetheless, this particular immune profile has opened a new window of treatments based on immunotherapy that have significantly improved the clinical outcome of melanoma patients. Still, positive and complete therapy responses have been limited, and this particular cancer continues to be a major clinical challenge. The transcriptomic signatures of those patients with clinical benefit and those with progressive disease have provided a more complete picture of the universe of interactions between the tumor and the immune system. In this review, we integrate the results of the immunotherapy clinical trials to discuss a novel understanding of the mechanisms guiding cancer immunosurveillance and immunoediting. A clear notion of the cellular and molecular processes shaping how the immune system and the tumor are continuously coevolving would result in the rational design of combinatory therapies aiming to counteract the signaling pathways and cellular processes responsible for immunoescape mechanisms and provide clinical benefit to immunotherapy nonresponsive patients.