Inclusion Criteria:

1. Understand and voluntarily sign an informed consent document

2. Age greater than or equal to 18 years at the time of signing Informed Consent

3. Be able to adhere to the study visit schedule and other protocol requirements

4. Histological documentation of malignant melanoma with evidence of metastatic disease

5. For the 10 patients enrolled at the MTD, at least one measurable lesion must be
present (see Appendix II)

6. ECOG performance status of 0, 1 or 2 (see Appendix I)

7. Laboratory tests within these ranges:

1. Absolute neutrophil count greater than or equal to 1,500/uL

2. Platelet count greater than or equal to 100,000/uL

3. Serum creatinine less than or equal to 1.5 mg/dL

4. Total bilirubin less that or equal to 1.5 mg.dL

5. AST (SGOT) / ALT (SGPT) less than or equal to to 2 times upper limit of normal
(ULN)

8. Women of childbearing potential (WCBP) must have a negative serum or urine pregnancy
test within 7 days of starting study drug.

In addition, sexually active WCBP must agree to use at least two methods of adequate
contraceptive (oral, injectable, or implantable hormonal contraceptive, tubal
ligation, intra-uterine device, barrier contraceptive with spermicide, contraceptive
skin patch or vasectomized partner) while on study drug

9. All acute adverse effects (excluding alopecia of any prior therapy must have resolved
to less than or equal to grade 1 (NCI CTCAE v3.0)

10. Patients must be able to take medications orally

Exclusion Criteria:

1. Pregnant or lactating females

2. Any serious medical condition, including psychiatric illnesses that will prevent the
patient from signing the informed consent or place the patient at an unacceptable
risk if he/she participates in the study.

3. Prior treatment with systemic chemotherapy. Patients who have received prior
immunotherapy, including thalidomide, or radiotherapy remain eligible.

Lesions within a prior field of radiation may only be used as indicator lesions if
there has been evidence of disease progression at that site.

4. Prior history of malignancies (except for basal cell or squamous cell carcinoma of
the skin or carcinoma in situ of the cervix or breast) unless the patient has been
free of the disease for at least 3 years.

5. Use of thalidomide or biologic response modifier therapy within 14 days of Day 1,
Cycle 1

6. Prior greater than or equal to grade 2 allergic reaction to thalidomide

7. Prior desquamating rash while taking thalidomide

8. Any prior use of lenalidomide

9. Concurrent use of any other anti-cancer agents

10. Radiation or surgical treatment of melanoma within 28 days of starting study
treatment

11. Active infection

12. Central nervous system (CNS) metastases

13. Patients with > grade-2 neuropathy

14. Patients with known HIV positivity or AIDS-related illness