Here we describe the rational design, computer-aided virtual ligand docking and synthesis of 19 nonpeptidic compounds designed to inhibit histone deacetylases and kill melanoma cells. Compounds were derived from cysteine, fused at the S-terminus to 4-butanoyl hydroxamate, and at the N-terminus to 4-(dimethylamino)benzoic acid. The latter was extended by coupling to amines to form a small library of prospective anti-cancer compounds. Four compounds were cytotoxic at sub-micromolar concentrations against cells of a particularly aggressive human melanoma (MM96L), and nine compounds showed selectivities of >or=5:1 for killing human melanoma instead of normal human fibroblast cells. The most active compounds were shown to cause hyperacetylation of histones due to inhibition of histone deacetylases. Further refinement of these compounds may produce an anti-tumor drug suitable for treating melanoma.