Abstract The identification of blood-borne biomarkers correlating with melanoma patient survival remains elusive. Novel techniques such as mass cytometry could help to identify melanoma biomarkers, allowing simultaneous detection of up to 100 parameters. However, the evaluation of multiparametric data generated via time-of-flight mass cytometry requires novel analytical techniques because the application of conventional gating strategies currently used in polychromatic flow cytometry is not feasible. In this study, we have employed 38-channel time-of-flight mass cytometry analysis to generate comprehensive immune cell signatures using matrix boolean analysis in a cohort of 28 stage IV melanoma patients and 17 controls. Clusters of parameters were constructed from the abundance of cellular phenotypes significantly different between patients and controls. This approach identified patient-specific combinatorial immune signatures consisting of high-resolution subsets of the T cell, NK cell, B cell, and myeloid compartments. An association with superior survival was characterized by a balanced distribution of myeloid-derived suppressor cell-like and APC-like myeloid phenotypes and differentiated NK cells. The results of this study in a discovery cohort of melanoma patients suggest that multifactorial immune signatures have the potential to allow more accurate prediction of individual patient outcome. Further investigation of the identified immune signatures in a validation cohort is now warranted.