Epigenetic regulation of tumor suppressor genes (TSGs) has been shown to play a central role in melanomagenesis. By integrating gene expression and methylation array analysis we identified novel candidate genes frequently methylated in melanoma. We validated the methylation status of the most promising genes using highly sensitive Sequenom Epityper assays in a large panel of melanoma cell lines and resected melanomas, and compared the findings with those from cultured melanocytes. We found transcript levels of UCHL1, COL1A2, THBS1 and TNFRSF10D were inversely correlated with promoter methylation. For THBS1 and UCHL1 the effect of this methylation on expression was confirmed at the protein level. Identification of these candidate TSGs and future research designed to understand how their silencing is related to melanoma development will increase our understanding of the etiology of this cancer and may provide tools for its early diagnosis.