Abstract Background The heterogeneous behavior of patients with melanoma makes prognostication challenging. To address this, a gene expression profile (GEP) test to predict metastatic risk was previously developed. This study evaluates the GEP’s prognostic accuracy in an independent cohort of cutaneous melanoma patients. Methods This multi-center study analyzed primary melanoma tumors from 523 patients, using the GEP to classify patients as Class 1 (low risk) and Class 2 (high risk). Molecular classification was correlated to clinical outcome and assessed along with AJCC v7 staging criteria. Primary endpoints were recurrence-free (RFS) and distant metastasis-free (DMFS) survival. Results The 5-year RFS rates for Class 1 and Class 2 were 88% and 52%, respectively, and DMFS rates were 93% versus 60%, respectively (P < 0.001). The GEP was a significant predictor of RFS and DMFS in univariate analysis (hazard ratio [HR] = 5.4 and 6.6, respectively, P < 0.001 for each), along with Breslow thickness, ulceration, mitotic rate, and sentinel lymph node (SLN) status (P < 0.001 for each). GEP, tumor thickness and SLN status were significant predictors of RFS and DMFS in a multivariate model that also included ulceration and mitotic rate (RFS HR = 2.1, 1.2, and 2.5, respectively, P < 0.001 for each; and DMFS HR = 2.7, 1.3 and 3.0, respectively, P < 0.01 for each). Conclusions The GEP test is an objective predictor of metastatic risk and provides additional independent prognostic information to traditional staging to help estimate an individual’s risk for recurrence. The assay identified 70% of stage I and II patients who ultimately developed distant metastasis. Its role in consideration of patients for adjuvant therapy should be examined prospectively.