Inclusion Criteria:

- Able to provide written informed consent

- Eastern Cooperative Oncology Group (ECOG) Performance Status of 2 or less

- Men with histologically documented previously treated hormone refractory
adenocarcinoma of the prostate; mixed histology and rare subtypes histology of
prostate cancer are allowed only in phase 1 portion of trial

- Patients must be on an luteinizing-hormone-releasing hormone (LHRH) agonist or have
undergone surgical castration

- Patients must have already failed or progressed after treatment with a
docetaxel-based regimen; patients who were unable to tolerate docetaxel are eligible
in phase 1 portion of trial

- Creatinine clearance >= 45 by Cockcroft-Gault formula

- Total bilirubin =< upper limit of normal (ULN)

- Aspartate aminotransferase (AST) < 2 x ULN

- Alanine aminotransferase (ALT) < 2 x ULN

- Hepatic alkaline phosphatase < 2 x ULN (< 5.0 x ULN for subjects with known bone
metastases)

- Absolute neutrophil count > 1,500/mm^3

- Platelets > 100,000/mm^3

- Hemoglobin >= 9.0 g/dL

- Able to adhere to the study visit schedule and other protocol requirements

- No serious disease or condition that, in the opinion of the investigator, would
compromise the patient's ability to participate in the study

- All study participants must be registered into the mandatory RevAssist program, and
be willing and able to comply with the requirements of RevAssist

- Able to take aspirin (81 or 325 mg) daily as prophylactic anticoagulation (patients
intolerant to acetylsalicylic acid [ASA] may use warfarin or low molecular weight
heparin)

- Men must agree to use a latex condom during sexual contact with females of
childbearing potential (FCBP) even if they have had a successful vasectomy

- Male subject agrees to use an acceptable method for contraception for the duration of
the study; EKG at baseline, if abnormal, not medically relevant

- Electrocardiogram (EKG) at baseline, if abnormal, not medically relevant

Exclusion Criteria:

- Treatment with a cytotoxic chemotherapy or investigational drug within 30 days before
Day 1 of study treatment; palliative radiation therapy is allowed, as long as a
radiated lesion is not used to assess response rate, and the radiation occurred
greater than 4 weeks prior to enrollment

- Known positive for human immunodeficiency virus (HIV) or infectious hepatitis, type
A, B or C or active Hepatitis

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

- Known hypersensitivity to thalidomide, lenalidomide or cyclophosphamide

- Active infection at the start of lenalidomide

- Myocardial infarction within 6 months prior to enrollment or has New York Heart
Association (NYHA) Class III or IV heart failure uncontrolled angina, severe
uncontrolled ventricular arrhythmias, or electrocardiographic evidence of acute
ischemia or active conduction system abnormalities; prior to study entry, any
electrocardiograph (EKG) abnormality at screening has to be documented by the
investigator as not medically relevant

- History of life threatening or recurrent thrombosis/embolism; patients may
participate if they are adequately anti-coagulated during the treatment

- Patient has > Grade 2 peripheral neuropathy within 14 days before enrollment

- Any evidence of severe or uncontrolled systemic disease (e.g., unstable or
uncompensated respiratory, cardiac, hepatic, or renal disease)

- Any unresolved chronic toxicity greater than common terminology criteria (CTC) Grade
2 from previous anticancer therapy (except alopecia)

- Evidence of any other significant clinical disorder or laboratory finding that makes
it undesirable for the subject to participate in the trial