Cancer stem cells and the misregulation of epigenetic modifications have been identified to possess a determinative role in carcinogenesis. The purpose of this study was to investigate the expression profile of EZH2 and H3K4me2 and H3K27me3, which constitute stem cell-like "bivalent" domains, in cutaneous malignant melanoma. A comparative analysis of their immunohistochemical expression between the invasion front (IF) and the inner tumor mass was also evaluated. Immunohistochemical methodology was performed on sections of 89 melanoma lesions from 79 patients. The 3 markers studied were identified in the cell nuclei of melanoma cells, nevus cells, and normal epidermal keratinocytes. A specific distribution pattern of H3K4me2 and H3K27me3 was found, as stronger levels were localized at the IF of the tumor (P = 0.034 and P < 0.01, respectively). In general, H3K4me2 and H3K27me3 levels were lower in metastatic with respect to primary melanoma cases (P = 0.0065 and P = 0.027, respectively). Advanced melanoma demonstrated significantly lower H3K4 immunohistochemical expression than did cases of lowest Clark level (I) (P = 0.038) or low Breslow depth (≤1 mm; P < 0.001). Furthermore, EZH2 expression in melanoma cells was higher compared with that in nevus cells (P = 0.02). A positive correlation between EZH2-H3K27me3 (P = 0.03) and H3K4me2-H3K27me3 (P < 0.01) in melanoma cells was also found. Our results suggest the possibility that combined immunohistochemical expression of EZH2, H3K4me2, and H3K27me3 might identify cancer cells with potential stem cell properties, particularly at the IF of this malignancy. This hypothesis should be further investigated, as many of the epigenetic changes are reversible via pharmacologic manipulations and new therapies, overpassing the resistance of advanced melanoma, may be developed.