Inclusion Criteria:

- Histologically confirmed diagnosis of adenocarcinoma of the prostate (M0) with
evidence of biochemical relapse after local therapy (i.e., surgery, radiation
therapy, or both.) Baseline PSA must be greater or equal to 1 ng/ml.

- Confirmed rise in PSA shown by 2 PSA values at least 1 month apart, higher than a
reference value noted within 6 months of study entry. Interim PSA values during the
immediate pre-study six-month interval may demonstrate a "fluctuation" including a
decline, however the study baseline PSA must have shown a rise within the pre-study
6-months period. Baseline PSA's must be determined within 4 weeks of study entry.

- All previous local modalities of treatment, including radiation and surgery, must
have been discontinued at least 4 weeks prior to treatment in this study. May have
received prior systemic chemotherapy, hormonal therapy, biologic or vaccine therapy.
All treatment must have been discontinued for more than 6 months prior to study
entry.

- Patients receiving intermittent hormonal therapy for their rising PSA state are
considered eligible if testosterone level is above 150 ng/dl and treatment was
discontinued greater than 6 months

- No clinical or radiological evidence of distant metastases (excluding prostascint
scan).

- Serum testosterone > 150 ng/ml

- Disease free of prior malignancies for more than 5 years with exception of currently
treated basal cell, squamous cell carcinoma of the skin, or carcinoma "in situ" of
the breast.

- Able to take aspirin (81 or 325 mg) daily as prophylactic anticoagulation (patients
intolerant to ASA may use low molecular weight heparin). Lenalidomide increases the
risk of thrombotic events in patients who are at high risk or with a history a
thrombosis, in particular when combined with other drugs known to cause thrombosis.

Exclusion Criteria:

- Any serious medical condition, laboratory abnormality, or psychiatric illness that
would prevent the subject from signing the informed consent form.

- 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 to thalidomide.

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

- Any prior use of Revlimid® (CC-5013).

- Concurrent use of other anti-cancer agents or treatments.

- Known brain metastases.

- Known positive for HIV or infectious hepatitis, type A, B or C.

- Any evidence of metastatic disease.

- Any increase in PSA while receiving neo-adjuvant or adjuvant therapy or intermittent
hormonal therapy.

- More than one prior biologic or vaccine therapy