Cutaneous melanoma is a highly aggressive skin cancer whose treatment and prognosis are critically affected by the presence of metastasis. In this study, we address the following issue: which gene transcripts and what kind of interactions between them can allow to predict nonmetastatic from metastatic melanomas with a high level of accuracy? We carry out a meta-analysis on the first gene expression set of the Leeds melanoma cohort, as made available online on 11 May 2016 through the ArrayExpress platform with MicroArray Gene Expression number 4725. According to the authors, primary melanoma mRNA expression was measured in 204 tumours using an illumina DASL HT12 4 whole-genome array. The tumour transcripts were selected through a recently proposed predictive-based regression algorithm for gene-network selection. A set of 64 equivalent models, each including only two gene transcripts, were each sufficient to accurately classify primary tumours into metastatic and nonmetastatic melanomas. The sensitivity and specificity of the genomic-based models were, respectively, 4% (95% confidence interval: 0.11–21.95%) and 99% (95% confidence interval: 96.96–99.99%). The very high specificity coupled with a significantly large positive likelihood ratio leads to a conclusive increase in the likelihood of disease when these biomarkers are present in the primary tumour. In conjunction with other highly sensitive methods, this approach can aspire to be part of the future standard diagnosis methods for the screening of metastatic cutaneous melanoma. The small dimension of the selected transcripts models enables easy handling of large-scale genomic testing procedures. Moreover, some of the selected transcripts have an understandable link with what is known about cutaneous melanoma oncogenesis, opening a window on the molecular pathways underlying the metastatic process of this disease.