Inclusion Criteria:

          -  Patients must have histologically or cytologically confirmed stage IIIB or stage IV
             NSCLC with measurable disease at initial presentation prior to chemotherapy. See
             Section 8.4.1 for measurable disease parameters.

          -  Patients must have had a complete response (CR), partial response (PR) or stable
             disease (SD) after 4-6 cycles of first-line chemotherapy. Tumor response will be
             assessed by RECIST criteria version 1.1.

          -  Patients must have fully recovered from the acute toxic effects of all prior
             chemotherapy, or radiotherapy before entering this study.

               1. Myelosuppressive chemotherapy: At least 21 days elapsed from end of treatment
                  before registration (42 days if prior nitrosourea).

               2. Hematopoietic growth factors: At least 7 days since the completion of therapy
                  with a growth factor.

               3. Other: For agents that have known adverse events occurring beyond 7 days after
                  administration, this period must be extended beyond the time during which adverse
                  events are known to occur.

               4. XRT: > or = to 2 weeks for local palliative XRT (small port); 3 months must have
                  elapsed if 50% radiation of pelvis; 6 weeks must have elapsed if other
                  substantial bone marrow radiation.

          -  Patients must be > or = 18 years of age.

          -  ECOG performance status < or = to 1 (Karnofsky > 70%).

          -  Organ Functions: Patients must have normal organ and marrow function as defined below
             within 28 days of registration:

               1. Leukocytes > or = 3,000/uL

               2. Absolute neutrophil count > or = 1,500/uL

               3. Hemoglobin > or = 8 g/dL

               4. Platelets > or = 100,000/uL

               5. Total bilirubin 1.5X institutional upper limit of normal (ULN)

               6. AST (SGOT) and ALT (SGPT) 1.5X institutional ULN

               7. Creatinine clearance > or = 60 mL/min/1.73 m2 for patients with creatinine levels
                  > institutional normal

          -  All study participants must be willing and agree to be registered into the mandatory
             REVLIMID REMS program, and be willing and able to comply with the requirements of
             REVLIMID REM. REVLIMID REMS registration does not need to be complete to determine
             study eligibility.

          -  Females of childbearing potential (FCBP)* must have a negative serum or urine
             pregnancy test with a sensitivity of at least 50 mIU/mL within 10 - 14 days before
             registration. Treating investigator must affirm intention to perform another serum or
             urine UPT 24 hours before initiating lenalidomide treatment.

             *FCBP: A female of childbearing potential (FCBP) is a sexually mature female who: 1)
             has not undergone a hysterectomy or bilateral oophorectomy; or 2) has not been
             naturally postmenopausal (amenorrhea following cancer therapy does not rule out
             childbearing potential) 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 about pregnancy precautions, risks of fetal exposure
             and other risks. The counseling must be done before the initiation of the study and
             every 28 days before the study drug is dispensed to the subject. 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 she starts taking 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. See
             Appendix D: Risks of Fetal Exposure, Pregnancy Testing Guidelines and Acceptable Birth
             Control Methods.

          -  Able to take aspirin (81 mg) daily as prophylactic anticoagulation (Patients
             intolerant to ASA may use warfarin or low molecular weight heparin).

          -  Able to understand and willing to sign a written informed consent document.

          -  Life expectancy > or = 12 weeks

        Exclusion Criteria

          -  Concomitant Medications:

               1. Patients may not be receiving any other anti-cancer therapy.

               2. Patients may not be receiving any other investigational agents.

               3. Patients may not be receiving systemic steroids or other immunosuppressive drugs;
                  however, steroid containing inhaler may be allowed after discussing with the
                  Principal Investigator. Duration of 5 half-lives must have elapsed before the
                  study registration if the patient was on systemic steroids or other
                  immunosuppressive drugs.

          -  Patients with untreated brain metastasis, or with treated brain metastasis but
             requiring steroids.

          -  Patients with known EGFR mutation or EML-ALK fusion gene and with stage IV disease.

          -  History of allergic reactions attributed to compounds of similar chemical or biologic
             composition to lenalidomide or thalidomide.

          -  The development of erythema nodosum if characterized by a desquamating rash while
             taking thalidomide or similar drugs.

          -  Uncontrolled inter-current illness including, but not limited to, ongoing or active
             infection, symptomatic congestive heart failure, myocardial infarction within the last
             6 months, unstable angina pectoris, cardiac arrhythmia, autoimmune disease or
             psychiatric illness/social situations that would limit compliance with study
             requirements.

          -  Pregnant or breastfeeding women are excluded from this study because lenalidomide has
             the potential for teratogenic or abortifacient effects. Because there is an unknown
             but potential risk for adverse events in nursing infants secondary to treatment of the
             mother with lenalidomide, breastfeeding should be discontinued if the mother is
             treated with lenalidomide.

          -  Known sera-positive for or active viral infection with human immunodeficiency virus
             (HIV), hepatitis B virus (HBV) or hepatitis C virus (HCV). Patients who are
             seropositive because of hepatitis B virus vaccine are eligible.

          -  Any other clinically significant medical condition and/or organ dysfunction that will
             interfere with the administration of the therapy according to this protocol or which,
             in the views of investigator, preclude combination chemotherapy.