The search for antimelanoma agents acting by terminal differentiation via the pigmentation pathway has so far been unsuccessful, in part because of tumor heterogeneity and loss of function of pigmentation genes. Some differentiation agents, however, have emerged as inhibitors of histone deacetylases (HDAC), with consequences for chromosome remodeling, cell cycle arrest and selective toxicity in cultured melanoma cells compared with normal melanocytes. Few effects have been found on pigmentation, except paradoxically the down-regulation of TRP-1. Of the many genes regulated by HDAC inhibitors, induction of p21(WAF1/Cip1) is the most consistent finding and is associated with G(1) or G(2) phase blocks. Some melanoma cell lines appear to lack an HDAC inhibitor-specific G(2) checkpoint and viability is thus compromised by dividing with inappropriately-modified chromatin. Most cultured melanoma cells undergo apoptosis following treatment with HDAC inhibitors, via a mitochondrial and caspase-dependent pathway. However, the molecular mechanism may vary with cell line and HDAC inhibitor class. Tumor selectivity cannot yet be attributed to specific types or levels of HDACs, nor has the possibility of acetylation of non-histone targets been excluded. Elucidation of these complexities may be rewarding, in terms of directing the multiple consequences of inhibiting histone deacetylation towards overcoming the therapeutic problems of melanoma heterogeneity and emergence of resistance. Success in the clinic may require combination with agents that synergize with the cell cycle blocking and pro-apoptotic action of HDAC inhibitors.