There is a need to identify molecular biomarkers of melanoma progression to assist the development of chemoprevention strategies to lower melanoma incidence. Using datasets containing gene expression for dysplastic nevi and melanoma or melanoma arising in a nevus, we performed differential gene expression analysis and regularized regression models to identify genes and pathways that were associated with progression from nevi to melanoma. A small number of genes distinguished nevi from melanoma. Differential expression of seven genes was identified between nevi and melanoma in three independent datasets. C1QB, CXCL9, CXCL10, DFNA5 (GSDME), FCGR1B, and PRAME were increased in melanoma, and SCGB1D2 was decreased in melanoma, compared to dysplastic nevi or nevi that progressed to melanoma. Further supporting an association with melanomagenesis, these genes demonstrated a linear change in expression from benign nevi to dysplastic nevi to radial growth phase melanoma to vertical growth phase melanoma. The genes associated with melanoma progression showed significant enrichment of multiple pathways related to the immune system. This study demonstrates (1) a novel application of bioinformatic approaches to aid clinical trials of melanoma chemoprevention and (2) the feasibility of determining a gene signature biomarker of melanomagenesis.