Differentiation of proliferative nodules in giant congenital nevi from melanoma arising within such nevi is an important diagnostic challenge. DNA methylation is a well-established epigenetic modification already observed in the earliest stages of carcinogenesis, which increases during melanoma progression. The ten-eleven translocation enzymes catalyze the oxidation of 5-methylcytosine to 5-hydroxymethylcytosine (5-hmC), which has recently been reported as an epigenetic hallmark associated with tumor aggressiveness and poor prognosis in a wide variety of cancers. In this study, we analyzed 12 proliferative nodules and 13 melanomas both arising in giant congenital nevi and matched results with a control group including 67 benign and malignant melanocytic lesions. Proliferative nodules displayed high 5-hmC expression levels (90.65%) compared with melanomas with almost complete loss of this marker (7.87%). We showed that low 5-hmC levels in melanomas correlate with downregulation of isocitrate dehydrogenase and ten-eleven translocation families of enzymes implicated in the cytosine methylation cycle. Simultaneously, these enzymes were overexpressed in proliferative nodules leading to strong 5-hmC expression. We emphasize the significance of 5-hmC loss for discrimination of melanomas from benign proliferative nodules arising within giant congenital nevi, and for establishing the correct diagnosis in ambiguous cases when histological and immunohistochemical characteristics are not sufficiently specific.