The primary objective of this study was to determine the safety, toxicity, and maximum tolerated dose of nanoparticle albumin-bound (nab)-paclitaxel as part of biochemotherapy for metastatic melanoma and to determine whether substituting nab-paclitaxel for less potent agents could increase response rates and duration. Treatment consisted of intravenous cisplatin (20 mg/m) on days 1-4, oral temozolomide (250 mg/m) on days 1-3, subcutaneous interferon-α (5×10 IU/m) on days 1-5, and continuous intravenous interleukin-2 (9×10 IU/m) for 96 h on days 1-4. A standard 3+3 dose escalation method was used; the nab-paclitaxel starting dose was 100 mg/m on day 1 and 70 mg/m on day 5. The treatment cycle was repeated every 3 weeks and toxicity was assessed weekly. Ten patients were enrolled. Dose-limiting toxicities included diarrhea, transaminasemia, and neutropenia. The maximum tolerated dose was not identified because the nab-paclitaxel dose on day 1 at the lowest planned dose (80 mg/m) caused dose-limiting toxicity in two of five patients. Of the nine patients who were evaluable for response, five had a partial response. The median time to disease progression was 5.30 months and the median overall survival was 8.73 months. Six patients developed central nervous system metastasis at a median of 5.33 months after treatment initiation. Biochemotherapy including nab-paclitaxel according to the doses and schedule regimen used in the present study has significant toxicity. Substituting dacarbazine with temozolomide did not prevent central nervous system metastasis in patients with metastatic melanoma.