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. Although spontaneous regression, likely due to immune defense activation, rarely occurs, we lack a biological rationale and predictive markers in 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 Q3 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. Although 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 a high frequency of CDKN2A homozygous deletions (P < 0.01). We observed a different prognosis between the subtypes (P = 0.01), with a particularly poor survival for patients harboring tumors of the proliferative subtype compared with the others (P = 0.003). Importantly, the clinical relevance of the subtypes was validated in an independent cohort of 44 stage III and IV melanomas. Moreover, low expression of an a priori defined gene set associated with immune response signaling was significantly associated with poor outcome (P = 0.001). Conclusions: Our data reveal a biologically based taxonomy of malignant melanomas with prognostic effect and support an influence of the antitumoral immune response on outcome.