Abstract Background High tumor mutational burden (TMB) is associated with a favorable outcome in metastatic melanoma patients treated with immune checkpoint inhibitors. However, data are limited in the adjuvant setting. As BRAF mutated patients have an alternative with targeted adjuvant therapy, it is important to identify predictive factors for relapse and recurrence-free survival (RFS) in patients receiving adjuvant anti-PD-1 antibodies. Methods We evaluated 165 melanoma patients who started adjuvant anti-PD-1 antibody therapy at our center between March 2018 and September 2019. The initial tumor stage was assessed at the beginning of therapy according to the 8th edition of the AJCC Cancer Staging Manual. Tumor and normal tissue of the high-risk stages IIIC/D/IV were sequenced using a 700 gene NGS panel. Results The tumor stages at the beginning of adjuvant anti-PD-1 therapy were as follows: N = 80 stage IIIA/B (48%), N = 85 stage IIIC/D/IV (52%). 72/165 patients (44%) suffered a relapse, 44/72 (61%) with only loco regional and 28/72 (39%) with distant metastases. Sequencing results were available from 83 to 85 patients with stage IIIC/D/IV. BRAF mutation status (HR 2.12, 95% CI 1.12–4.08; p = 0.022) and TMB (HR 7.11, 95% CI 2.19–23.11; p = 0.001) were significant and independent predictive factors for relapse-free survival (RFS). Conclusion BRAF mutation status and TMB were independent predictive factors for RFS. Patients with BRAF V600E/K mutation and TMB high had the best outcome. A classification based on BRAF mutation status and TMB is proposed to predict RFS in melanoma patients with adjuvant anti-PD-1 therapy.