Systemic treatment of metastatic melanoma is of low efficacy, and new therapeutic strategies are needed. Histone deacetylase inhibitors are supposed to restore the expression of tumor suppressor genes and induce tumor cell differentiation, growth arrest, and apoptosis. This study was aimed to evaluate the efficacy, safety, and pharmacokinetics of the histone deacetylase inhibitor pyridylmethyl-N-{4-[(2-aminophenyl)-carbamoyl]-benzyl}-carbamate (MS-275) in patients with pretreated metastatic melanoma. Patients with unresectable AJCC stage IV melanoma refractory to at least one earlier systemic therapy were randomized to receive MS-275 3 mg biweekly (days 1+15, arm A) or 7 mg weekly (days 1+8+15, arm B), in 4-week cycles. The primary study endpoint was objective tumor response, secondary endpoints were safety and time-to-progression. On the basis of Simon's two-stage design, the study initially allowed an entry of 14 patients per arm; if there was at least one responder, additional 33 patients were to be enrolled. Among 28 patients enrolled, no objective response was detected. Four (29%) patients in arm A and three (21%) patients in arm B showed disease stabilizations. Median time-to-progression was comparable in both arms with 55.5 versus 51.5 days, respectively; median overall survival was 8.84 months. Toxicity was mild to moderate with nausea (39%) and hypophosphatemia (29%) as the most frequently reported events. No treatment-related serious adverse events occurred. Single-agent treatment with MS-275 was well-tolerated and showed long-term tumor stabilizations, but no objective responses in pretreated metastatic melanoma. Further evaluation of MS-275 in combination schedules is warranted.