The purpose of this study is to find out what dose of lenalidomide is safe to use in combination with decitabine when given in people with myelodysplastic syndrome.

Myelodysplastic syndrome (MDS) is a group of different kinds of stem cell abnormalities. It is characterized by low blood counts and abnormal blood cell formation. These abnormal blood cells can cause fatigue, shortness of breath, infection, and bleeding. There is significant risk of developing acute leukemia in this disorder.

The only known curative therapy is an allogeneic bone marrow transplant of which the vast majority of patients with this disorder are not candidates. Currently three drugs have been approved for the treatment of MDS: azacytidine, decitabine and lenalidomide for low grade patients with a chromosome 5q abnormality. Azacytidine and decitabine have been demonstrated to improve blood counts, improve the quality of life, and decrease the risk of progression to AML or death in a sizable minority of MDS patients. A recent study of MDS patients who had responded clinically to decitabine revealed that their bone marrow biopsies still showed stromal abnormalities such as increased angiogenesis. Lenalidomide acts at the level of the stromal - marrow cell interaction. It is hypothesized that the combination of decitabine with lenalidomide may show synergistic results.

Inclusion Criteria:

• Understand and voluntarily sign an informed consent form.
• Age >/=18 years at the time of signing the informed consent form.
• Able to adhere to the study visit schedule and other protocol requirements.
• Myelodysplastic syndrome (documented by bone marrow biopsy) with IPSS score of Int-2 or High risk.
• All previous MDS therapy, including radiation, hormonal therapy and surgery, must have been discontinued at least 28 days prior to treatment in this study.
• ECOG performance status of </= 2 at study entry.
• Laboratory test results within these ranges: Serum creatinine </= 2.5 mg/dL x ULN, Total bilirubin </= 2.5 mg/dL x ULN, AST (SGOT) and ALT (SGPT) </= 3 x ULN.
• All study participants must be registered into the mandatory RevAssist® program, and be willing and able to comply with the requirements of RevAssist®.
• Females of childbearing potential must have a negative serum pregnancy test within 10-14 days prior to and again within 24 hours of prescribing lenalidomide and must either commit to continued abstinence from heterosexual intercourse or begin TWO acceptable methods of birth control, one highly effective method and one additional effective method AT THE SAME TIME, at least 28 days before she starts taking lenalidomide. Must also agree to ongoing pregnancy testing.
• Men must agree to use a latex condom during sexual contact even if they have had a successful vasectomy.
• Disease free of prior malignancies for >/= 3 years with exception of currently treated basal cell, squamous cell carcinoma of the skin, localized prostate cancer, or carcinoma "insitu" of the cervix or breast.

Exclusion Criteria:

• Any serious medical condition, laboratory abnormality, or psychiatric
• Pregnant or breast feeding females.
• Any condition, including the presence of laboratory abnormalities, which places the subject at unacceptable risk if he/she were to participate in the study or confounds the ability to interpret data from the study.
• Known hypersensitivity or reaction to thalidomide, lenalidomide or decitabine.
• Any prior use of lenalidomide.
• Concurrent use of other anti-cancer agents or anti-cancer treatments.
• Known positive for HIV or active infectious hepatitis, type A, B or C.
• History of thromboembolic event within past 6 months prior to enrollment.