The goal of this clinical research is to find the highest tolerable dose of Abraxane (nab-paclitaxel) when given directly to the area where the cancer is located. The safety of this drug will also be studied.

The Study Drug:

Nab-paclitaxel is designed to block cancer cells from dividing, which may cause them to die.

Study Drug Groups:

If you are found to be eligible to take part in this study, you will be assigned to a dose level of nab-paclitaxel based on when you joined this study. Up to 4 dose levels of nab-paclitaxel will be tested. The first group of participants will receive the lowest dose level. Each new group will receive a higher dose than the group before it, if no intolerable side effects were seen. This will continue until the highest tolerable dose of nab-paclitaxel is found.

Study Drug Administration:

During Cycles 1-6, you will admitted to the hospital the day before each time you are scheduled to receive the study drug. On the day after you are admitted (Day 1), you will have a catheter inserted into the hepatic artery (the major blood vessel that carries blood to the liver). You will be separately consented for this procedure, which will describe the procedure and its risks in detail. If the melanoma has spread to your skin, you may also be asked to take part in a separate laboratory study. In that study, you will have a tumor biopsy to check the concentration of a protein called SPARC in the tumor. Earlier clinical trials have shown that patients with tumors containing high levels of SPARC have better chance of the tumor shrinking with nab-paclitaxel treatment. You do not have to agree to the laboratory study in order to take part in this main study.

On Day 1 of Cycles 1-6, you will then receive nab-paclitaxel through the arterial catheter over 30 minutes. The catheter will be removed after you receive the study drug.

Your vital signs will be measured before and after you receive the study drug. You will be sent home from the hospital the next day if your vital signs are stable.

On Day 1 of Cycle 7 and beyond, you will receive the study drug through a catheter in your vein over 30 minutes. You will not need to stay in the hospital when you receive the study drug by vein.

On Day 1 of all cycles, before you receive the study drug, you will receive drugs to help to prevent for nausea and vomiting.

Each cycle is 3 weeks.

Study Visits:

On Days 1 and 21 (+ or - 4 days) of every cycle, the following tests and procedures will be performed:

• You will have a physical exam, including measurement of your weight.
• Your medical history will be recorded.
• You will be asked if you have experienced any side effects.
• Blood (about 1 tablespoon) will be drawn for routine tests.
• You will have a performance status evaluation.

On Days 8 and 15 all cycles, blood (about 1 tablespoon) will be drawn for routine tests.

Before each cycle of therapy, you will have a physical exam. Blood (about 2 tablespoons) will be drawn for routine tests.

Before every other cycle beginning with Cycle 3 (Cycles 3, 5, 7 and so on), you will have CT scans to check the status of the disease.

Length of Study:

You may continue to receive the study drug for as long as you are benefitting. You will be taken off study early if you experience intolerable side effects or the disease gets worse.

End-of-Study Visit:

Within 28 days after the last dose of study drug, you will have an end-of-study visit. The following tests and procedures performed:

• You will have a physical exam.
• You will be asked if you have experienced any side effects.
• You will have a chest x-ray, CT scans, and an ECG to check the status of the disease.
• Blood (about 1 tablespoon) and urine will be collected for routine tests.
• You will be asked about any new symptoms that you may have experienced after you stopped receiving the study drug.
• If the doctor thinks it is necessary, you will have an MRI to check the status of the disease.

This is an investigational study. Nab-paclitaxel is FDA approved and commercially available for the treatment of breast cancer when given by vein. Its use in liver cancer patients, as well as its administration into the hepatic artery, is investigational.

Up to 40 patients will take part in this study. All will be enrolled at M. D. Anderson.

Inclusion Criteria:

1. Patients must have histologic confirmation of malignant melanoma, and documented metastatic disease.
2. Patients must have at least one clearly measurable metastatic lesion in the liver that is more than 2cm in the largest dimension. Indicator lesions at least 2cm are chosen primarily to have changes in tumor measurement more accurately reflective of effect of therapy, or lack of it.
3. Patients must not have received prior systemic chemotherapy with regimens including taxanes. Prior adjuvant treatment with immunotherapy or vaccine therapy is allowed provided there is documentation of disease progression in the liver.
4. At least 4 weeks (28 days) since any prior immunotherapy, cytokine, biologic, vaccine therapy or tumor embolization in the liver and patients should have progressed during therapy. Patient must have recovered from any side effects before starting therapy on this protocol.
5. At least 4 weeks (28 days) since prior radiotherapy (if radiation therapy field covering > 20% of the bone marrow containing skeletal structures) and prior adjuvant therapy. Patient must have recovered from any side effects before starting therapy on this protocol.
6. Lesions being used to assess disease status may not have been radiated or if so, must have progressed during or after radiation therapy.
7. Patients must have Eastern Cooperative Oncology Group (ECOG) performance status of 0 - 2.
8. Patients must be >/= 18 years of age. The safety of NAB-Paclitaxel has not been studied in younger patients.
9. Patients must have normal serum total bilirubin level, transaminase levels (i.e., ALT and AST) no higher than 2.5 times the institution's upper normal limits. Patients must have adequate renal function: creatinine </= 1.5 mg/dL Patients must have adequate bone marrow function as defined by an absolute neutrophil count >/= 1,500/mm^3, platelet count >/= 100,000/mm^3 and hemoglobin >/= 9.0g/dL.
10. Life expectancy of at least 3 months.
11. Patients must sign an informed consent form indicating that they are aware of the investigational nature of this study and in keeping with the policies of the institution.

Exclusion Criteria:

1. Patients who have received prior systemic chemotherapy with regimens including taxanes.
2. Patients with history of central nervous system (CNS) metastasis prior to registering to this study.
3. Patients who are pregnant or nursing and patients who are not practicing an acceptable method of birth control. A negative pregnancy test (urine or serum) must be documented at baseline for women of childbearing potential. Patients may not breast-feed while on this study.
4. Patients with current active infections requiring anti-infectious treatment (e.g., antibiotics, antivirals, or antifungals).
5. Patients with current peripheral neuropathy of any etiology that is greater than grade one.
6. Patients with unstable or serious concurrent medical conditions are excluded. Examples include, but are not limited to, uncontrolled ventricular arrhythmia, recent (within 3 months) myocardial infarction, uncontrolled major seizure disorder, spinal cord compression, superior vena cava syndrome, or any psychiatric disorder that prohibits obtaining informed consent.
7. Patients must not have had major surgery including node dissection, resection of melanoma metastatic to an organ or other surgical procedures that require hospitalization and administration of general anesthesia within the past 14 days.
8. Patients must not receive any concurrent chemotherapy, radiotherapy, or immunotherapy while on study.
9. Known HIV disease or infection.
10. Patients with ascites are not eligible.