Primary melanomas >1 mm thickness are potentially curable by resection, but can recur metastatically. We assessed the prognostic value of the T-cell fraction (TCFr) and repertoire T-cell clonality, measured by high-throughput sequencing of the T-cell receptor β-chain in T2–T4 primary melanomas (n = 199). TCFr accurately predicted progression-free survival and was independent of thickness, ulceration, mitotic rate and age. TCFr was second only to tumor thickness in its predictive value, using a gradient-boosted model. For accurate progression-free survival prediction, adding TCFr to tumor thickness was superior to adding any other histopathological variable. Furthermore, a TCFr >20% was protective regardless of tumor ulceration status, mitotic rate or presence of nodal disease. TCFr is a quantitative molecular assessment that predicts metastatic recurrence in primary melanoma patients whose disease has been resected surgically. The present study suggests that a successful T-cell-mediated, antitumour response can be present in primary melanomas.