Melanoma brain metastasis (MBM) represents a frequent complication of cutaneous melanoma. Despite aggressive multi-modality therapy, patients with MBM often have a survival rate of <1 year. Alteration in DNA methylation is a major hallmark of tumor progression and metastasis; however, it remains largely unexplored in MBM. In this study, we generated a comprehensive DNA methylation landscape through the use of genome-wide copy number, DNA methylation and gene expression data integrative analysis of melanoma progression to MBM. A progressive genome-wide demethylation in low CpG density and an increase in methylation level of CpG islands according to melanoma progression were observed. MBM-specific partially methylated domains (PMDs) affecting key brain developmental processes were identified. Differentially methylated CpG sites between MBM and lymph node metastasis (LNM) from patients with good prognosis were identified. Among the most significantly affected genes were the HOX family members. DNA methylation of HOXD9 gene promoter affected transcript and protein expression and was significantly higher in MBM than that in early stages. A MBM-specific PMD was identified in this region. Low methylation level of this region was associated with active HOXD9 expression, open chromatin and histone modifications associated with active transcription. Demethylating agent induced HOXD9 expression in melanoma cell lines. The clinical relevance of this finding was verified in an independent large cohort of melanomas (n = 145). Patients with HOXD9 hypermethylation in LNM had poorer disease-free and overall survival. This epigenome-wide study identified novel methylated genes with functional and clinical implications for MBM patients.