Cellular heterogeneity in cancer is linked to disease progression and therapy response, although the mechanisms regulating distinct cellular states within the tumours are not well understood. To address this, we identified melanin pigment content as a major source of phenotypic and functional heterogeneity in melanoma and compared RNAseq data from high pigmented cells (HPCs) displaying substantially reduced clonogenicity in vitro and tumorigenicity in vivo and low pigmented melanoma cells (LPC) with higher tumorigenicity, revealing the polycomb repressor complex protein, EZH2, as a master regulator of these states. EZH2 protein, but not RNA expression, was found to be upregulated in LPCs and inversely correlated with melanin in pigmented patient melanomas. Surprisingly, conventional EZH2 methyltransferase inhibitors, GSK126 and EPZ6438, had no effect on LPC survival, clonogenicity and pigmentation, despite fully inhibiting methyltransferase activity. In contrast, EZH2 silencing by siRNA or EZH2 protein degradation by DZNep or MS1943 treatment significantly inhibited cell growth in LPCs by hampering ribosome biogenesis. In addition, a decline in EZH2 protein level induces a pigmented cell phenotype by upregulating melanin biosynthesis. As proteasomal inhibitor MG132 treatment induced EZH2 protein levels in HPCs we explored differentially regulated ubiquitin system proteins in HPC vs LPCs. Both biochemical assays and animal studies demonstrated that the E2 conjugating enzyme UBE2L6 negatively regulates EZH2 protein stability via ubiquitination at the K381 residue in LPCs in cooperation with UBR4. UBE2L6 has been shown to be downregulated significantly in LPCs by UHRF1-mediated CpG methylation. Targeting this UHRF1/UBE2L6/UBR4 axis may be an optimal method to enforce the HPC state in melanoma in which conventional EZH2 inhibitors are ineffective.