Inclusion Criteria:

* Patients must have morphologically confirmed diagnosis of myelodysplastic syndrome (MDS) or chronic myelomonocytic leukemia (CMML) based on one of the following:

* French-American-British (FAB) classifications:

* Refractory anemia with excess blasts (RAEB - defined as having 5-20% myeloblasts in the bone marrow)
* Chronic myelomonocytic leukemia (CMML) with 10-19% myeloblasts in the bone marrow and/or 5-19% blasts in the blood
* World Health Organization (WHO) classifications:

* Refractory anemia with excess blasts-1 (RAEB-1 - defined as having 5-9% myeloblasts in the bone marrow)
* Refractory anemia with excess blasts-2 (RAEB-2 - defined as having 10-19% myeloblasts in the bone marrow and/or 5-19% blasts in the blood)
* Chronic myelomonocytic leukemia-1 (CMML-1 - defined as having \< 10% myeloblasts in the bone marrow and/or \< 5% blasts in the blood)
* Chronic myelomonocytic leukemia-2 (CMML-2 - defined as having 10-19% myeloblasts in the bone marrow and/or 5-19% blasts in the blood) OR
* International prognostic score (IPSS) of intermediate 2 (1.5-2.0 points) or high (\>= 2.5 points); a score of intermediate 1 (0.5-1.0 points) is only allowable in the setting of \>= 5% myeloblasts
* NOTE: Patients with acute myeloid leukemia (AML) are not eligible
* Procedures to obtain specimens for establishing baseline disease must be done within 30 days prior to registration
* Patients must not have received lenalidomide, azacitidine, vorinostat, or decitabine as treatment previously; any hematopoietic growth factors must be stopped for at least 14 days prior to registration; patients may have received low-dose cytarabine for MDS treatment previously, but they must have discontinued its use for at least 28 days prior to registration; patients may have received prior hydroxyurea per CMML treatment previously, but they must have discontinued its use for at least 7 days prior to registration; these patients will not be eligible if white blood cell (WBC) \> 30,000/mm\^3
* Patients must not have received radiation therapy, chemotherapy, or cytotoxic therapy to treat conditions other than MDS within 12 months prior to registration
* Patients must not have undergone prior allogeneic stem cell or bone marrow transplantation at any time; patients that have undergone an autologous stem cell transplant are eligible
* Patients must not have used or be using histone deacetylase (HDAC) inhibitor agents for anticancer treatment
* Patients may not have received agents such as valproic acid for epilepsy within 30 days prior to registration
* Patients must have Zubrod performance status of 0-2
* Patients must not have any pre-existing neurotoxicity/neuropathy of \>= grade 2 according to the National Cancer Institute (NCI) Common Toxicity Criteria version 4.0, or prior \>= grade 3 allergic reaction/hypersensitivity or rash to thalidomide, that has not resolved to \< grade 2
* Patients must not have any serious medical condition, laboratory abnormality, or psychiatric illness that, in the view of the treating physician, would place the participant at an unacceptable risk if he or she were to participate in the study or would prevent that person from giving informed consent
* Patients must not have history of thromboembolic event or other condition requiring current use of anticoagulation with Coumadin (warfarin) or low molecular-weight heparin
* Patients must not have known or suspected hypersensitivity to mannitol
* Patients must receive a 12-lead electrocardiogram (EKG), chest x-ray or computed tomography (CT) scan, serum creatinine, complete metabolic panel including serum glutamic oxaloacetic transaminase (SGOT) or serum glutamate pyruvate transaminase (SGPT), electrolytes, and bilirubin testing within 28 days prior to registration in order to establish baseline measurements; questions regarding patient safety in regards to results of these tests should be directed to the study chair
* Females of childbearing potential (FCBP) must have a negative serum or urine pregnancy test with a sensitivity of at least 25 mIU/mL within 10 - 14 days prior to registration; FCBP must agree to have a second pregnancy test within 24 hours prior to starting cycle 1 if randomized to receive lenalidomide

* Further, patients commit to the following if they are randomized to receive lenalidomide: FCBP 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 starting lenalidomide; FCBP must also agree to ongoing pregnancy testing; men must agree to use a latex condom during sexual contact with a FCBP, even if they have had a successful vasectomy; a FCBP is a sexually mature woman who: 1) has not undergone a hysterectomy or bilateral oophorectomy; or 2) has not been naturally postmenopausal for at least 24 consecutive months (i.e., has had menses at any time in the preceding 24 consecutive months); all patients must be counseled by a trained counselor every 28 days about pregnancy precautions and risks of fetal exposure
* NOTE: Patients not randomized to receive lenalidomide will not be required to undergo serial pregnancy testing or lenalidomide counseling after registration
* No prior malignancy is allowed except for adequately treated basal cell (or squamous cell) skin cancer, in situ cervical cancer, or other cancer for which the patient has been disease-free for three years
* Cytogenetics requirements:

* Southwestern Oncology Group (SWOG) (and other sites not affiliated with Alliance or Eastern Cooperative Oncology Group \[ECOG\]-American College of Radiology Imaging Network \[ACRIN\]): Pretreatment cytogenetics must be performed on all patients; collection of pretreatment specimens must be completed within 30 days prior to registration to S1117; specimens must be submitted to the site's preferred Clinical Laboratory Improvement Amendments (CLIA)-approved cytogenetics laboratory; reports of the results must be submitted as described; note that cytogenetics are required at other timepoints; NOTE: National Cancer Institute of Canada Clinical Trials Group (NCIC CTG) sites may submit specimens to College of American Pathologists (CAP) or Ontario Laboratory Accreditation (OLA)-approved laboratories providing the lab is licensed to perform fluorescent in situ hybridization (FISH) analysis
* Alliance: Alliance patients must enroll on Cancer and Leukemia Group B (CALGB) 8461, the cytogenetics protocol; CALGB 8461 provides sample procurement and submission instructions to Alliance-approved institutional cytogeneticists; note that cytogenetics are required at other timepoints
* ECOG-ACRIN: Pretreatment cytogenetics must be performed on all patients; collection of pretreatment specimens must be completed within 30 days prior to registration to S1117; specimens must be submitted to the site's preferred CLIA-approved cytogenetics laboratory; karyotypes and reports must be submitted for review to the Mayo Clinic Cytogenetics Laboratory in Rochester; note that cytogenetics testing is required at other timepoints
* Banking requirements:

* SWOG, Alliance and ECOG-ACRIN (and other sites not affiliated with NCIC CTG): Patients must be offered participation in specimen banking; with patient consent, specimens must be submitted as outlined
* Alliance: (Temporarily Closed 2/28/14): As of February 28, 2014, CALGB 9665 has been temporarily closed, so Alliance patients under consideration for S1117 are NOT to be registered to CALGB 9665 and no specimens for patients enrolled after February 28, 2014 are to be submitted via this ancillary study; these patients should submit specimens per SWOG instructions; patients already enrolled on CALGB 9665 should continue to submit specimens per instructions in CALGB 9665
* NCIC CTG: NCIC CTG patients must be offered participation in specimen submission and banking; with patient consent, specimens must be submitted as outlined
* All patients or their legally authorized representative must be informed of the investigational nature of this study and must sign and give written informed consent in accordance with institutional and federal guidelines
* As a part of the Oncology Patient Enrollment Network (OPEN) registration process the treating institution's identity is provided in order to ensure that the current (within 365 days) date of institutional review board approval for this study has been entered in the system