Background: Gene expression profiling data for human primary cutaneous melanomas are scarce because of the lack of retrospective collections of frozen tumors. To identify differentially expressed genes that may be involved in melanoma progression and prognosis, we investigated the relationship between gene expression profiles and clinical outcome in a cohort of patients with primary melanoma. Methods: Labeled complementary RNA (cRNA) from each tissue sample was hybridized to a pangenomic 44K 60-mer oligonucleotide microarray. Class comparison and class prediction analyses were performed to identify genes whose expression in primary melanomas was associated with 4-year distant metastasis-free survival among 58 patients with at least 4 years of follow-up, distant metastasis, or death. Results were validated immunohistochemically at the protein level in 176 independent primary melanomas from patients with a median clinical follow-up of 8.5 years. Survival was analyzed with a Cox multivariable model and stratified log-rank test. All statistical tests were two-sided. Results: We identified 254 genes that were associated with distant metastasis-free survival of patients with primary melanoma. These 254 genes include genes involved in activating DNA replication origins, such as minichromosome maintenance genes and geminin. Twenty-three of these genes were studied at the protein level; expression of five (MCM4, P = .002; MCM3, P = .030; MCM6, P = .004; KPNA2, P = .021; and geminin, P = .004) was statistically significantly associated with overall survival in the validation set. In a multivariable Cox model adjusted for tumor thickness, ulceration, age, and sex, expression of MCM4 (hazard ratio [HR] of death = 4.04, 95% confidence interval [CI] = 1.39 to 11.76; P = .010) and MCM6 (HR of death = 7.42, 95% CI = 1.99 to 27.64; P = .003) proteins was still statistically significantly associated with overall survival. Conclusion: We identified 254 genes whose expression was associated with metastatic dissemination of cutaneous melanomas. These genes may shed light on the molecular mechanisms underlying poor prognosis in melanoma patients.