Based on the poor impact on overall survival obtained by systemic chemotherapy in metastatic melanoma and the identification of many melanoma antigens recognized by T cells, in the last decade many efforts have been devoted to the development of active specific immunotherapy as a promising systemic treatment for this neoplastic disease. A number of Phase I-II clinical trials have been performed with different vaccination approaches that included whole tumor cells, antigen peptides, antigen-pulsed dendritic cells, recombinant viruses, plasmids or naked DNA, and heat-shock proteins. Despite some promising immunological and clinical results obtained in these studies, melanoma-specific vaccines have altogether failed to prove their efficacy in the few large Phase III randomized clinical trials performed. Nonetheless, the possibility of activating the human immune system to recognize and destroy tumor cells remains a challenging investigative field, considering that the new knowledge of the intricate cellular and molecular mechanisms that regulate the immune function and tumor-host interactions may allow the development of new clinically relevant melanoma vaccination strategies.