Dysregulation of components of the ubiqutin system has been linked to many diseases including melanoma. This is vital since the post-translational modification of different proteins via direct ubiquitin attachment is an important process for various cellular processes. CYLD is a tumor suppressor gene and deubiquitinating enzyme, which can remove polyubiquitin chains from their specific substrate and interfere with different signaling pathways. CYLD is frequently downregulated or even lost in melanoma cell lines or tissues compared to melanocytes. Down-regulation of CYLD leads to sustained oncogenic signaling that promotes melanoma progression and metastasis. In this review, we summarize the recent insights into the mechanisms which are responsible for the down-regulation of CYLD levels in melanoma and the signaling interactions of the CYLD gene product in melanoma. We argue that these recent insights into CYLD function invite the development of novel molecular strategies for melanoma prevention and treatment.