Normal cell growth is characterized by a regulated epigenetic program that drives cellular activities such as gene transcription, DNA replication and DNA damage repair. Perturbation of this epigenetic program can lead to events such as mis-regulation of gene transcription and diseases such as cancer. To begin to understand the epigenetic program correlated to the development of melanoma, we performed a quantitative mass spectrometric analysis of histone posttranslational modifications mis-regulated in melanoma cell culture. Aggressive melanoma cells were found to have elevated histone H3 lysine 27 trimethylation (H3K27me3) as well as over-expressed methyltransferase EZH2 that adds the specific modification. The altered epigenetic program that led to elevated H3K27me3 in melanoma cell culture was found to directly silence transcription of the tumor suppressor gene RUNX3. The elevated level of H3K27me3 and silencing of RUNX3 transcription was also validated in advanced stage human melanoma tissues. The study presented underscores the utility of using high resolution mass spectrometry to identify mis-regulated epigenetic programs in diseases such as cancer, which could ultimately lead to the identification of biological markers for diagnostic and prognostic applications.