This phase II trial studies how well lenalidomide works in combination with rituximab in treating participants with stage III-IV non-Hodgkin lymphoma that is growing slowly. Lenalidomide is designed to change the body's immune system. It may also interfere with the development of tiny blood vessels that help support tumor growth, which may prevent the growth of cancer cells. Monoclonal antibodies, such as rituximab, may interfere with the ability of cancer cells to grow and spread. Giving lenalidomide and rituximab may work better in participants with indolent non-Hodgkin lymphoma.

PRIMARY OBJECTIVES:

I. To evaluate the overall response rate of lenalidomide in combination with rituximab in previously untreated indolent non-Hodgkin's lymphoma (NHL).

SECONDARY OBJECTIVES:

I. To evaluate the toxicity of lenalidomide in combination with rituximab in previously untreated indolent non-Hodgkin's lymphoma.

OUTLINE: Participants are assigned to 1 of 2 drug schedules.

SCHEDULE A: Participants receive lenalidomide orally (PO) on days 1-21 and rituximab intravenously (IV) over 4-8 hours on day 1 of courses 1-12. Courses repeat every 28 days for up to 12 courses in the absence of disease progression or unacceptable toxicity.

SCHEDULE B: Participants receive lenalidomide PO on days 2-22 and rituximab IV over 4-8 hours on days 1, 8, 15, and 22 of course 1 and on day 1 of all subsequent courses. Courses repeat every 28 days for up to 12 courses in the absence of disease progression or unacceptable toxicity.

After completion of study treatment, participants are followed up every 6 months.

Inclusion Criteria:

1. Understand and voluntarily sign an informed consent form.
2. Age >/= 18 at the time of signing the informed consent form.
3. Able to adhere to the study visit schedule and other protocol requirements.
4. Untreated indolent non-Hodgkin's lymphoma stage III-IV including small lymphocytic lymphoma, marginal zone lymphoma, grade 1 or 2 follicular lymphoma. (prior radiation for localized disease allowed).
5. At least one measurable lesion according to the International workshop standardized response criteria for non-Hodgkin's lymphomas (IWG) greater than 1.5cm.
6. ECOG performance status of </= 2 at study entry.
7. Laboratory test results within these ranges: Absolute neutrophil count >/= 1.5 x 10^9/L; Platelet count >/=100 x 10^9/L; Serum creatinine </= 2.0 mg/dL; Total bilirubin </=1.5 mg/dL; AST (SGOT) and ALT (SGPT) </=2 x ULN or </=5 x ULN if hepatic metastases are present.
8. Disease free of prior malignancies for >/= 5 years with exception of currently treated basal cell, squamous cell carcinoma of the skin, or carcinoma "insitu" of the cervix or breast, or localized prostate cancer treated with curative intent.
9. All study participants must be registered into the mandatory RevAssist® program, and be willing and able to comply with the requirements of RevAssist®.
10. 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 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 4 weeks before she starts taking lenalidomide. FCBP must also agree to ongoing pregnancy testing.
11. Men must agree to use a latex condom during sexual contact with a female of child bearing potential even if they have had a successful vasectomy.
12. For patients with bulky disease (tumors >5cm) must be able to take aspirin (81 mg or 325 mg) daily as prophylactic anticoagulation (patients intolerant to ASA may use warfarin or low molecular weight heparin.

Exclusion Criteria:

1. Any serious medical condition, laboratory abnormality, or psychiatric illness that would prevent the subject from signing the informed consent form.
2. Pregnant or breast feeding females.
3. 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.
4. Use of any chemotherapy or experimental therapy within 28 days of enrollment.
5. Known hypersensitivity to thalidomide.
6. The development of erythema nodosum if characterized by a desquamating rash while taking thalidomide or similar drugs.
7. Any prior use of lenalidomide.
8. Concurrent use of other anti-cancer agents or experimental treatments.
9. Known positive for HIV or infectious hepatitis type B or C. (Hepatitis B core antibody can be positive if Hep B surface antigen is negative and no HBV DNA in blood, indicating a cleared infection.)