The goal of this clinical research study is to learn if tesetaxel can help to control metastatic melanoma. The safety of this drug will also be studied.

The Study Drug:

Tesetaxel is designed to block cancer cells from dividing, which may cause them to die.

Study Groups:

If you are found to be eligible to take part in this study, you will be assigned to 1 of 2 Groups based on when you enroll in this study. Each group has 2 "stages."

Group A:

A total of 27 patients will be enrolled in Group A and will receive a 40mg dose of tesetaxel, adjusted for individual body weight. For Group A, 13 patients will be enrolled in Stage 1. If at least 1 patient has a response to the 40 mg dose of tesetaxel, 14 additional patients will be enrolled in Stage 2 at the same dose level.

Group B:

A total of 27 patients will be enrolled in Group B and will receive a 50mg dose of tesetaxel, adjusted for individual body weight. For Group B, 13 patients will be enrolled in Stage 1 while researchers are waiting to see if patients in Group A respond to the study drug. If at least 1 patient has a response to the 50 mg dose of tesetaxel, 14 additional patients will be enrolled in Stage 2 at the same dose level.

Study Drug Administration:

No matter which Group you are assigned to, you will take tesetaxel capsules by mouth in the morning with water (6 ounces) on Day 1 of each 21-day study cycle. You must not eat or drink anything except water (fast) for at least 4 hours before taking tesetaxel. After fasting for 4 hours and taking tesetaxel, you may eat an average sized meal.

Before you take tesetaxel, you will receive drugs to prevent nausea and vomiting. The study doctor will discuss this with you. If you have a rash or allergic reaction, you may be receive an antihistamine and/or corticosteroid. If you develop a low number of white blood cells or red blood cells, you may be given growth factor drugs or receive transfusions. These drugs may be given by mouth or vein.

Study Visits:

On Day 1 of all Cycles:

-Your medical history, including any side effects you may have had and any drugs you may be taking, will be recorded.

On Day 9 (+/- 1 day) and again on Day 20 (+/- 2 days) of all Cycles:

• Any side effects you may have had and any drugs you may be taking will be recorded.
• Blood (about 2 teaspoons) will be drawn for routine tests.

Within 5 days before the start of cycles 3, 5, 7 and every other cycle thereafter:

• You will have a CT scan of the chest, stomach, and hip areas.
• Photographs of any melanoma on your skin will be taken.
• Any side effects you may have had and any drugs you may be taking will be recorded.

After the last dose of tesetaxel, blood (about 2 teaspoons) will be drawn for routine tests.

Within 3 weeks after the last dose of tesetaxel:

• You will have a CT scan of the chest, stomach, and hip areas.
• Photographs of any melanoma on your skin will be taken.
• Any side effects you may have had and any drugs you may be taking, will be recorded.

Length of Study:

You may continue taking the study drug for as long as the doctor thinks it is in your best interest. You will no longer be able to take the study drug if the disease gets worse or intolerable side effects occur.

Follow-Up Visits:

If the melanoma does not get worse while you are on study, you will have visits every 2 months for up to 12 months after your first dose of study drug. At these visits:

• You will have a CT scan of the chest, stomach, and hip areas.
• Photographs of any melanoma on your skin will be taken.
• Any side effects you may have had and any drugs you may be taking, will be recorded.
• You will be asked about any treatment you may be receiving.

If the disease gets worse while you are on study, you will have follow up phone calls every 2 months for up to 12 months after your first dose of study drug. During these calls, you will be asked how you are feeling and about any therapy you are receiving. These calls should take about 5 minutes.

This is an investigational study. Tesetaxel is not FDA approved or commercially available. It is currently being used for research purposes only.

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

Inclusion Criteria:

1. At least 18 years of age.
2. Histologically confirmed diagnosis of melanoma.
3. Progressive disease that is not surgically resectable, or metastatic Stage IV disease.
4. Measurable disease.
5. Serum LDH </= 1.1 times the upper limit of normal (x ULN).
6. Eastern Cooperative Oncology Group performance status 0 or 1.
7. Treatment with 1 prior regimen (including cytotoxic chemotherapy, immunotherapy, radiation therapy, or cytokine, biologic, or vaccine therapy) as first-line treatment for metastatic disease. (Administration of interleukin-2 or interferon as adjuvant therapy is allowed and is not to be considered in determining the 1 prior treatment regimen administered as first-line treatment for metastatic disease.)
8. Adequate bone marrow, hepatic, and renal function, as evidenced by: a) Absolute neutrophil count (ANC) >/= 1500/mm^3; b) Platelet count >/= 100,000/mm^3; c) Hemoglobin >/= 9 g/dL without need for hematopoietic growth factor or transfusion support; d) Aspartate aminotransferase (AST) </= 2.5 x ULN or, in the presence of liver metastasis, </= 5 x ULN; e) Alanine aminotransferase (ALT) </= 2.5 x ULN or, in the presence of liver metastasis, </= 5 x ULN f. Total bilirubin </= 1.5 x ULN;
9. (Continued # 8) g) Alkaline phosphatase </= 2.5 x ULN or, in the presence of liver metastasis, </= 5 x ULN or, in the presence of bone metastasis, </= 10 x ULN; h) Serum creatinine </= 1.5 x ULN; i) Serum albumin >/= 3.0 g/dL; j) Prothrombin time (PT) </= 1.5 x ULN (or international normalized ratio [international normalized ratio (INR)] </=1.3); k) Partial thromboplastin time (PTT) </= 1.5 x ULN.
10. At least 3 weeks and recovery from effects of prior surgery or other therapy with an approved or investigational agent.
11. Ability to swallow an oral solid-dosage form of medication.
12. A negative serum pregnancy test within 7 days prior to the first dose of study medication in women of childbearing potential (that is, all women except for those who are post menopause for > 1 year or who have a history of hysterectomy or surgical sterilization).
13. Agreement to use a highly effective form of contraception (ie, one that has a failure rate of < 1%) throughout the treatment phase of the study in women of childbearing potential (that is, all women excluding those who are post menopause for > 1 year or who have a history of hysterectomy or surgical sterilization) and sexually active men
14. Written informed consent and authorization to use and disclose health information.
15. Ability to comprehend and to comply with the requirements of the study.

Exclusion Criteria:

1. History or presence of brain metastasis or leptomeningeal disease.
2. Primary ocular or mucosal melanoma.
3. Second cancer (except for adequately treated basal cell or squamous cell skin cancer, in situ cervical cancer, or other cancer for which the subject has been disease-free for 5 or more years)
4. Human immunodeficiency virus infection based on history of positive serology.
5. Significant medical disease other than cancer, including but not limited to uncontrolled diabetes mellitus, active angina or heart failure, uncontrolled hypertension, or an active psychiatric condition that would prevent consistent and compliant participation in the study
6. Organ allograft.
7. Presence of neuropathy > Grade 1.
8. Prior treatment with a taxane or other tubulin-targeted agent (eg, indibulin) other than a vinca alkaloid.
9. Need for other anticancer treatment (such as chemotherapy, radiation therapy, or biologic therapy with an approved or investigational agent) while receiving protocol therapy.
10. Need to continue any regularly-taken medication that is a potent inhibitor or inducer of the CYP3A pathway or P-glycoprotein activity.
11. Less than 2 weeks since use of a medication or ingestion of an agent that is a potent inhibitor or inducer of the CYP3A pathway or P-glycoprotein.
12. Pregnancy or lactation.

Initiation of therapy through end of treatment (through 30 days after the last dose of study medication), up to 7 cycles of 21 day therapy.