Phase II Study of Adenovirus/PSA Vaccine in Men With Recurrent Prostate Cancer After Local Therapy APP21

Inclusion Criteria:

* Men with prostate cancer who have received prior local therapy (radical prostatectomy or definitive radiation therapy) and have biochemical (PSA) relapse without evidence of radiographic or clinical metastatic disease.
* For men who had prior prostatectomy, the surgery must have occurred at least 6 months prior to initiation of treatment.
* For men who had prior definitive radiation therapy, radiation must have been completed at least 1 year prior to initiation of treatment.
* Exhibit at least three separate rises in serum PSA, at least one month apart with differences \>/= 0.03 ng/ml and a total PSA of \>0.2 ng/ml.
* Have a PSA doubling time of \>/= 6 months if the baseline serum PSA was \>2 ng/ml.
* Negative bone scans.
* Negative CT scans of abdomen and pelvis (no evidence of soft tissue lesions \>/= 1 cm).
* Scans must be obtained within 6 weeks of entry into the trial (initiation of treatment).
* Written informed consent.
* Age \>/= 18 years.
* Required laboratory values \[obtained within 2 weeks of study entry (initiation of treatment)\].
* Serum creatinine \</= 2.0 mg/dL
* Adequate hematologic function: granulocytes \>/= 1800 per mm3, platelets \>/= 100,000 per mm3, WBC \>/= 3700, and lymphocytes \>/= 590.
* Adequate hepatocellular function: AST \<3x upper limit of normal and bilirubin \<1.5 mg/dl (unless bilirubin elevation is consistent with Gilbert's syndrome).
* PSA used as an eligibility criterion must be drawn within 42 days prior to injection number 1 and will be redrawn on Day 1 for use as a baseline value.

Exclusion Criteria:

* Candidates for salvage radiation therapy unless the patient refuses.
* Active or unresolved clinically significant infection.
* Parenteral antibiotics \<7 days prior to initiation of treatment.
* Evidence of prior or current CNS metastases. Specific imaging is not necessary in the absence of signs or symptoms.
* Co-morbid medical conditions which would result in a life expectancy (participation) of less than 1 year.
* Patients with compromised immune systems; congenital, acquired, or drug-induced (immunosuppressive agents) will be excluded from the study. Use of prednisone at doses higher than 10 mg daily (or equipotent steroid doses) for more than 7 days within the last 3 months is not allowed.
* No-pre-existing malignancies that required treatment within the past 5 years except for basal or squamous cell cancers of the skin.
* Prior systemic therapies for prostate cancer not allowed (hormonal therapy, including but not limited to LHRH agonists, antiandrogens, ketoconazole or chemotherapy - mitoxantrone/taxanes/estramustine, etc.) except when patients stopped hormone therapy two or more years prior to enrollment and currently have normal testosterone levels; patients in Arm B, undergoing androgen depletion therapy during the vaccination will be eligible.
* Prior participation in any vaccine studies for non-infectious diseases.
* The inability to understand the language and the clinical protocol.
* Allergy or religious objection to pork products; Gelfoam is produced from pork.