Immune-checkpoint blockade has revolutionized cancer therapy. In particular, inhibition of programmed cell death protein 1 (PD-1) has been found to be effective for the treatment of metastatic melanoma and other cancers. Despite a dramatic increase in progression-free survival, a large proportion of patients do not show durable responses. Therefore, predictive biomarkers of a clinical response are urgently needed. Here we used high-dimensional single-cell mass cytometry and a bioinformatics pipeline for the in-depth characterization of the immune cell subsets in the peripheral blood of patients with stage IV melanoma before and after 12 weeks of anti-PD-1 immunotherapy. During therapy, we observed a clear response to immunotherapy in the T cell compartment. However, before commencing therapy, a strong predictor of progression-free and overall survival in response to anti-PD-1 immunotherapy was the frequency of CD14+CD16−HLA-DRhi monocytes. We confirmed this by conventional flow cytometry in an independent, blinded validation cohort, and we propose that the frequency of monocytes in PBMCs may serve in clinical decision support.