The proteostasis network (PN) is a collection of protein folding and degradation pathways that spans cellular compartments and acts to preserve the integrity of the proteome. The differential expression of PN genes is a hallmark of many cancers, and the inhibition of protein quality control factors is an effective way to slow cancer cell growth. However, little is known about how the expression of PN genes differs between patients and how this impacts survival outcomes. To address this, we applied unbiased hierarchical clustering to gene expression data obtained from primary and metastatic cutaneous melanoma (CM) samples and found that two distinct groups of individuals emerge across each sample type. These patient groups are distinguished by the differential expression of genes encoding ATP-dependent and ATP-independent chaperones, and proteasomal subunits. Differences in PN gene expression were associated with increased levels of the transcription factors, MEF2A, SP4, ZFX, CREB1 and ATF2, as well as markedly different survival outcomes. However, surprisingly, similar PN alterations in primary and metastatic samples were associated with discordant survival outcomes in patients. Our findings reveal that the expression of PN genes demarcates CM patients and highlights several new proteostasis sub-networks that could be targeted for more effective suppression of CM within specific individuals.