Adjuvant systemic therapies are now routinely used following resection of stage III melanoma, however accurate prognostic information is needed to better stratify patients. We use differential expression analyses of primary tumours from 204 RNA-sequenced melanomas within a large adjuvant trial, identifying a 121 metastasis-associated gene signature. This signature strongly associated with progression-free (HR = 1.63, p = 5.24 × 10-5) and overall survival (HR = 1.61, p = 1.67 × 10-4), was validated in 175 regional lymph nodes metastasis as well as two externally ascertained datasets. The machine learning classification models trained using the signature genes performed significantly better in predicting metastases than models trained with clinical covariates (pAUROC = 7.03 × 10-4), or published prognostic signatures (pAUROC < 0.05). The signature score negatively correlated with measures of immune cell infiltration (ρ = -0.75, p