Aberrant methylation of promoter regions involved in silencing of tumor suppressor genes is a key feature of many human cancers including melanoma. These DNA methylation events occur early in cancer development, increase with progression, and may therefore serve as biomarkers for the detection and staging of cancer. In our study, we used an epigenomic reactivation screening approach including Combined Bisulfite Restriction Analyses (COBRA) assays to identify novel methylation markers in late-stage melanoma. Two human xenograft melanoma models have been used to identify genes methylated in cancer and reactivated upon treatment with a histone deacetylase inhibitor. Gene expression analysis and promoter scanning for DNA methylation by COBRA assays and bisulfite sequencing were used to identify candidate genes. The methylation status of the CpG island promoter region of genes related to melanoma pathophysiology in skin, lymph node, and visceral metastatic metastases in 28 patients (samples n=35) were assessed. These methylation markers have been evaluated in melanoma metastasis tissue and in control samples from normal skin. The screening in in-vitro and in-vivo systems for methylated genes in melanoma samples showed 10 candidate genes. Using COBRA assays, we detected a methylation pattern in the promoter region of 10 genes with two genes (BASP1, CDH11), together with the patient's age and the log-S100B-level at biopsy, constructing a descriptor with a trend to correlate with shorter time to death.