Dysplastic nevi are melanocytic lesions that represent an intermediate stage between common nevus and melanoma. Histopathological distinction of dysplastic nevus from melanoma can be challenging and there is a requirement for molecular diagnostic markers. In this study, we examined promoter CpG island methylation of a selected panel of genes, identified in a genome-wide methylation screen, across a spectrum of 405 melanocytic neoplasms. Promoter methylation analysis in common nevi, dysplastic nevi, primary melanomas, and metastatic melanomas demonstrated progressive epigenetic deregulation. Dysplastic nevi were affected by promoter methylation of genes that are frequently methylated in melanoma but not in common nevi. We assessed the diagnostic value of the methylation status of five genes in distinguishing primary melanoma from dysplastic nevus. In particular, CLDN11 promoter methylation was specific for melanoma, as it occurred in 50% of primary melanomas but in only 3% of dysplastic nevi. A diagnostic algorithm that incorporates methylation of the CLDN11, CDH11, PPP1R3C, MAPK13, and GNMT genes was validated in an independent sample set and helped distinguish melanoma from dysplastic nevus (area under the curve 0.81). Melanoma-specific methylation of these genes supports the utility as epigenetic biomarkers and could point to their significance in melanoma development.