PURPOSE: The incidence of malignant melanoma is increasing worldwide in fair-skinned populations. Melanomas respond poorly to systemic therapy, and metastatic melanomas inevitably become fatal. While spontaneous regression, likely due to immune defense activation, rarely occurs, we lack a biological rationale and predictive markers selecting patients for immune therapy. Experimental design: We performed unsupervised hierarchical clustering of global gene expression data from stage IV melanomas in 57 patients. For further characterization we used immunohistochemistry of selected markers, genome-wide DNA copy number analysis, genetic and epigenetic analysis of the CDKN2A locus and NRAS/BRAF mutation screening. RESULTS: The analysis revealed four distinct subtypes with gene signatures characterized by expression of immune response, pigmentation differentiation, proliferation or stromal composition genes. Even though all subtypes harbored NRAS and BRAF mutations, there was a significant difference between subtypes (p<0.01), with no BRAF/NRAS wild-type samples in the proliferative subtype. Additionally, the proliferative subtype was characterized by high frequency of CDKN2A homozygous deletions (p<0.01). We observed different prognosis between the subtypes (p=0.01), with a particularly poor survival for patients harboring tumors of the proliferative subtype compared to the others (p = 0.003). Importantly, the clinical relevance of the subtypes was validated in an independent cohort of 44 stage III/IV melanomas. Moreover, low expression of an a priori-defined gene set associated to immune response signaling was significantly associated to poor outcome (p=0.001). CONCLUSIONS: Our data reveal a biologically-based taxonomy of malignant melanomas with prognostic impact and support an influence of the anti-tumoral immune response on outcome.