Overall survival (OS) in patients with early-stage malignant melanoma differs. To date, there are no established prognostic markers. We aimed to contribute to a better understanding of potential prognostic immunohistochemical markers for risk stratification.161 surgically resected early-stage malignant melanomas (stage pT1 and pT2) were analyzed for expression of 20 different proteins using immunohistochemistry. The results were correlated with OS. The cohort was randomly split into a discovery and a validation cohort.High Bcl-2 expression, high nuclear S100A4 expression as well as a Ki67 proliferation index of ≥ 20 % were associated with shorter OS. Strong MITF immunoreactivity was a predictor for favorable prognosis. A combination of these four markers resulted in a multi-marker score with significant prognostic value in multivariate survival analysis (HR: 3.704; 95 % CI 1.484 to 9.246; p = 0.005). Furthermore, the score was able to differentiate a low-risk group with excellent OS rates (five-year survival rate: 100 %), an intermediate-risk group (five-year survival rate: 81.8 %) and a high-risk group (five-year survival rate: 52.6 %). The prognostic value was confirmed within the validation cohort.Combined immunohistochemical analysis of Bcl-2, nuclear S100A4, Ki67 and MITF could contribute to better risk stratification of early-stage malignant melanoma patients.