Inclusion Criteria:

- Biopsy-proven KS involving skin with or without visceral involvement either newly
diagnosed or refractory to or intolerant of one or more prior therapies

- Patients must have cutaneous lesion(s) amenable to four 3 mm tumor biopsies during
the study (either 4 separate lesions measuring > 4 mm each OR 2 separate lesions
measuring > 8 mm each) and at least five additional lesions measurable for assessment
with no improvement over the past month

- Serologic documentation of HIV infection by any of the FDA-approved tests

- Karnofsky performance status >= 60%

- Hemoglobin >= 8 g/dL

- Absolute neutrophil count (ANC) >= 1,000 cells/mm^3

- Platelet count >= 100,000/mm^3

- Calculated (method of Cockcroft-Gault) creatinine clearance (CrCl) >= 60 mL/min in
the Phase I and CrCl >= 30 mL/min in the Phase II (creatinine clearance may also be
obtained by the 24-hour collection method at the investigator's discretion)

- Total bilirubin should be =< 1.5x ULN; if, however, the elevated bilirubin is felt to
be secondary to Atazanavir therapy, patients will be allowed to enroll on protocol if
the total bilirubin is =< 3.5 mg/dL provided that the direct bilirubin is normal

- AST (SGOT) and ALT (SGPT) =< 3x ULN

- Life expectancy >= 3 months

- Ability and willingness to give informed consent

- 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
and again within 24 hours prior to starting Cycle 1 of lenalidomide; further, they
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,
during receipt of lenalidomide, and 28 days after discontinuation of 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; all patients must be counseled at a minimum of every 28 days about
pregnancy precautions and risks of fetal exposure

- Patients must, in the opinion of the investigator, be capable of complying with the
protocol

- All patients must be on antiretroviral therapy for HIV infection with CD4 count >
50/mm^3 and viral load < 2,000 copies/mL; patients must be on a stable regimen for at
least 12 weeks prior to study entry; patients may receive any FDA approved
antiretroviral therapy except for zidovudine

- There should be no evidence for improvement in KS in the 3 months prior to study
entry, unless there is evidence for progression of KS in the 4 weeks immediately
prior to study entry

- If antiretroviral regimen contains zidovudine and viral load is suppressed (as
measured by HIV viral load =< 200/mL), then antiretroviral therapy must be
adjusted to a less toxic therapy not containing zidovudine and enrollment may
proceed without waiting 12 weeks; if on zidovudine-containing therapy and viral
load is not suppressed (as measured by HIV viral load >= 200/mL), then
antiretroviral therapy must be adjusted to a less toxic regimen allowing for
optimal viral suppression and must demonstrate stability for at least 12 weeks
prior to study entry

- Patients with any history of PE or DVT or predisposing clotting risk factors must be
on anticoagulation at therapeutic dosing

Exclusion Criteria:

- Concurrent, acute, active opportunistic infection other than oral thrush or genital
herpes within 14 days of enrollment

- Patients for whom front-line cytotoxic therapy is indicated (i.e. symptomatic
visceral or pulmonary KS or symptomatic KS impairing functional status)

- Concurrent neoplasia requiring cytotoxic therapy

- Acute treatment for an infection (other than oral thrush or genital herpes) or other
serious medical illness within 14 days of study entry

- Anti-neoplastic treatment for KS (including chemotherapy, radiation therapy, local
therapy including topical 5-FU, biological therapy, or investigational therapy)
within four weeks of study entry

- Any steroid treatment except for that required for replacement therapy in adrenal
insufficiency or inhaled steroids for the treatment of asthma

- Patient is =< 2 years free of another primary malignancy; exceptions include the
following:

- Basal cell skin cancer

- Cervical carcinoma in situ

- Anal carcinoma in situ

- Previous local therapy of any KS-indicator lesion unless the lesion has clearly
progressed since treatment; any prior local treatment to indicator lesions regardless
of the elapsed time should not be allowed unless there is evidence of clear-cut
progression of said lesion

- Use of any investigational drug or treatment within 4 weeks prior to enrollment

- Physical or psychiatric conditions that in the estimation of the investigator place
the patient at high risk of toxicity or non-compliance

- Female patients who are pregnant or breast-feeding

- Patients with a history of DVT or PE within 1 year

- Patients requiring blood transfusions to maintain Hgb eligibility

- Patients on erythropoietin-stimulating agents (ESA) unless also on therapeutic
anticoagulation

- Patients with CD4 < 50 mm^3 and/or viral load > 2,000 copies/mL

- Patients on estrogen therapy unless also on therapeutic anticoagulation