Malignant melanoma arises through a series of genetic and epigenetic events. A more profound understanding of the biology of metastatic melanoma should greatly aid in the development of new and effective treatments. Currently, avenues being pursued to improve treatment of metastatic melanoma include dendritic cell vaccines and other vaccination strategies, tyrosine kinase inhibitors, adoptive transfer of ex vivo stimulated T cells, and, as reviewed here, epigenetic approaches. The "methylator phenotype", with inactivation by promoter hypermethylation of numerous genes in malignant melanoma cell lines and primary tumors (p16, PTEN, RASSF1, estrogen receptor, retinoic acid receptor beta, SOCS1 and -2, MGMT etc.) offers a strong rationale for treatment approaches based on the use of DNA demethylating agents. The clinical literature on treatment of metastasized malignant melanoma with either 5-azacytidine or 5-aza-2'-deoxycytidine (decitabine) is reviewed. Future trials in malignant melanoma with these compounds might profit from prolonged low-dose exposure, since they unfold their full effects not immediately but with a certain delay, which may be associated with their DNA demethylating activity. Combinations of DNA demethylation agents with either histone deacetylase inhibitors, interleukin-2, chemotherapy or tamoxifen have been embarked on both in in vitro models of melanoma and recent clinical trials. The in vitro synergism between inhibitors of DNA methylation and histone deacetylation strongly invites a systematic study of combinations of both groups of agents. Up-regulation of cancer testis antigens by epigenetic therapy in melanoma also offers a very strong rationale to place these drugs and schedules within a larger treatment concept of immunotherapy which may include also T cell activation e.g. by interleukin-2, and vaccination strategies. In conclusion, the epigenome of malignant melanoma, with a well-established in vitro reversal potential, holds promise as a novel molecular target.