Despite the introduction of novel targeted therapies, chemotherapy still remains the primary treatment for metastatic melanoma in poorly funded healthcare environments or in case of disease relapse, with no reliable molecular markers for progression-free survival (PFS) available. As chemotherapy primarily eliminates cancer cells by apoptosis, we here evaluated if the expression of key apoptosis regulators (Bax, Bak, Bcl-2, Bcl-xL, Smac, Procaspase-9, Apaf-1, Procaspase-3 and XIAP) allows prognosticating PFS in stage III/IV melanoma patients. Following antibody validation, marker expression was determined by automated and manual scoring of immunohistochemically stained tissue microarrays (TMAs) constructed from treatment-naive metastatic melanoma biopsies. Interestingly and counter-intuitively, low expression of the pro-apoptotic proteins Bax, Bak and Smac indicated better prognosis (log-rank p < 0.0001, p = 0.0301 and p = 0.0227 for automated and p = 0.0422, p = 0.0410 and p = 0.0073 for manual scoring). These findings were independently validated in the cancer genome atlas (TCGA) metastatic melanoma cohort (TCGA-SKCM) at transcript level (log-rank p = 0.0004, p = 0.0104 and p = 0.0377). Taking expression heterogeneity between the markers in individual tumour samples into account allowed defining combinatorial Bax, Bak, Smac signatures that were associated with significantly increased PFS (p = 0.0002 and p = 0.0028 at protein and transcript level, respectively). Furthermore, combined low expression of Bax, Bak and Smac allowed predicting prolonged PFS (> 12 months) on a case-by-case basis (area under the receiver operating characteristic curve (ROC AUC) = 0.79). Taken together, our results therefore suggest that Bax, Bak and Smac jointly define a signature with potential clinical utility in chemotherapy-treated metastatic melanoma.