Cutaneous melanoma (CM) is the fourth tumor in frequency, and that whose incidence increases faster. In half of the cases, CM arises from pre-existing nevi. CM is a highly heterogeneous tumor, whose degree of differentiation varies among different hosts, and such heterogeneity is probably based on the accumulation of mutations that determine transitions from normal melanocytic stem cells → mutated benign melanocytic stem cells → malignant melanocytic stem cells → clonogenic melanocytic cells. These populations may express different antigens and would therefore trigger the proliferation of different T and B cell clones. Early diagnosis is the clue for the cure of CM; when visceral metastatic disease is established, the prognosis is somber. This is especially so since CM is quite resistant to chemotherapy, and some of the reasons for such resistance will be discussed here. However, CM has proved to be sensitive to immunological effectors, although the mechanism of such sensitivity is still being investigated. These effectors range from therapeutic vaccines, in vitro expanded cytotoxic lymphocytes, cytokines, and monoclonal antibodies. Finally, we will discuss new therapeutic approaches that include the combination of immune modulators and vaccines which are being assayed in light of recent tumor immunology research.