The primary objectives of the study are:

• To evaluate feasibility, safety and tolerance of 6 months administration of Revlimid at 5mg/day and 25mg/day, given orally in subjects with prostate cancer with evidence of biochemical relapse (M0) following local treatment (i.e., surgery or radiation).
• To assess the rate of PSA (prostatic specific antigen) progression at 6 months after treatment with 5mg/day and 25mg/day of Revlimid (CC-5013) in patients with evidence of biochemical relapse after local therapy.

The secondary objectives of the study are:

• To provide preliminary assessments on the effects of Revlimid (CC-5013) at 5mg/day and 25mg/day on various PSA constructs in the subject population (i.e., PSADT [Prostatic Specific Antigen Doubling Time] and PSA slope) by comparing pre and post treatment patterns in each arm.
• To evaluate preliminary pharmacodynamic correlations between serum revlimid concentrations and toxicity, PSA constructs and other evidence of disease progression.

Carcinoma of the prostate in the most commonly diagnosed malignancy among men in this country with approximately 232,090 new cases expected to be diagnosed in 2005. Unfortunately, despite local treatment, many men will demonstrate evidence of PSA recurrence. At the present time, there is no standard treatment fo these patients. The management of patients with PSA recurrence remains greatly controversial. Androgen deprivation is frequently employed in patients with evidence of rising PSA levels despite the fact that the effects on quantity and quality of life of androgen deprivation therapy at this stage, remains un-established. Toxicity of androgen deprivation therapy is a major factor to be considered in the decision process of employing the modality of treatment in patients with no symptoms associated with this disease. Because patients with biochemical relapse are mostly asymptomatic and typically have long survivals and disease free survivals, mush of the focus of new drug development has been with the use of non-cytotoxic compounds. This study is intended to provide preliminary evidence of a biological effect in a dose response manner assessing the effects of Revlimid (CC-5013) on PSA.

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 (ASA 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

Baseline characteristics were only recorded for patients who entered the study.

Collected monthly, up to 44 months