Purpose: Patients with stage I/IIA cutaneous melanoma (CM) are currently not eligible for adjuvant therapies despite uncertainty in relapse risk. Here, we studied the ability of a recently developed model which combines clinicopathologic and gene expression variables (CP-GEP) to identify stage I/IIA melanoma patients who have a high risk for disease relapse. Patients and methods: Archival specimens from a cohort of 837 consecutive primary CMs were used for assessing the prognostic performance of CP-GEP. The CP-GEP model combines Breslow thickness and patient age, with the expression of eight genes in the primary tumour. Our specific patient group, represented by 580 stage I/IIA patients, was stratified based on their risk of relapse: CP-GEP High Risk and CP-GEP Low Risk. The main clinical end-point of this study was five-year relapse-free survival (RFS). Results: Within the stage I/IIA melanoma group, CP-GEP identified a high-risk patient group (47% of total stage I/IIA patients) which had a considerably worse five-year RFS than the low-risk patient group; 74% (95% confidence interval [CI]: 67%–80%) versus 89% (95% CI: 84%–93%); hazard ratio [HR] = 2.98 (95% CI: 1.78–4.98); P < 0.0001. Of patients in the high-risk group, those who relapsed were most likely to do so within the first 3 years. Conclusion: The CP-GEP model can be used to identify stage I/IIA patients who have a high risk for disease relapse. These patients may benefit from adjuvant therapy.