High malignancy and early metastasis are hallmarks of melanoma. Here, we report that the transcription factor Snail1 inhibits expression of the tumor suppressor CYLD in melanoma. As a direct consequence of CYLD repression, the protooncogene BCL-3 translocates into the nucleus and activates Cyclin D1 and N-cadherin promoters, resulting in proliferation and invasion of melanoma cells. Rescue of CYLD expression in melanoma cells reduced proliferation and invasion in vitro and tumor growth and metastasis in vivo. Analysis of a tissue microarray with primary melanomas from patients revealed an inverse correlation of Snail1 induction and loss of CYLD expression. Importantly, tumor thickness and progression-free and overall survival inversely correlated with CYLD expression. Our data suggest that Snail1-mediated suppression of CYLD plays a key role in melanoma malignancy.