Inclusion Criteria

Patients are eligible if they have:

- Histologic diagnosis of adenocarcinoma of the prostate;

- At least 3 months but no more than 8 years prior to study entry, undergone a radical
prostatectomy for stage T1b – T3c, N0-N1, M0 disease, with or without
subsequent adjuvant or salvage radiation therapy. Patients who experience their
first PSA recurrence within 2 years post completion of initial therapy of curative
intent are eligible without consideration of the Gleason score of the tumor
specimen.* Patients who experience their first PSA relapse between 2 and 8 years
post completion of initial therapy of curative intent are eligible only if the
Gleason score of the tumor specimen was > 7; (* For patients who received adjuvant
radiation, the date of the final dose of radiotherapy is used to mark the date of
completion of therapy of curative intent. For patients who received salvage
radiation for post-operative PSA recurrence but no adjuvant radiation, the date of
surgery marks the date of completion of therapy of curative intent.)

- Therapeutic PSA response to primary therapy below 0.4 ng/mL;

- Tumor specimen positive for PAP, the vaccine’s target. Immunohistological
staining of a specimen from the surgically excised tumor for expression of PAP is
conducted by IMPATH, and may be completed even after LH-RH-analogue placement, as
long as a positive (+) result is confirmed prior to randomization (Week 0). If a
slide of the tumor cannot be obtained from the pathology archive, a chart record from
a PRE-SURGERY blood sample showing serum PAP elevated above the upper limit of the
local reference range may serve as a proxy.

- Experienced PSA relapse while not currently receiving androgen ablation therapy.
Specifically, on record must be 2 PSA values separated by at least 3 months, both in
the detectable range (>0.5 ng/mL), showing an increase of at least 0.3 ng/mL between
the 2 measurements. The first of these 2 PSA values must rise above a previously
recorded post-operative nadir value (which may be an undetectable PSA). In patients
who received androgen ablation for a previous PSA relapse, PSA must have increased to
a level at least 25% above the nadir observed while on this therapy and to an
absolute level of at least 3 ng/mL;

- Prior hormone treatment for an earlier episode of PSA relapse is neither an exclusion
nor an inclusion requirement for study entry. Patients who have previously been
treated with adjuvant or salvage radiation following radical prostatectomy, or with
either LH-RH-analogue (i.e., leuprolide or goserelin acetate) or non-steroidal
anti-androgen therapy (i.e., bicalutamide 150 mg/day) for a prior PSA relapse, may
enter the study provided:

- post-prostatectomy PSA was never > 20 ng/mL;

- PSA was not rising while receiving adequately dosed hormonal therapy;

- for any hormonal therapy received, the last effective day of androgen
deprivation was at least 6 months prior to study entry;

- Confirmed M0; a bone scan with no evidence of osseous metastasis must be on record,
dated within 6 months prior to entry into the study;

- Estimated life-expectancy, inclusive consideration of co-morbidities, of at least 1
year;

- ECOG performance status of 0 or 1;

- Ability to understand the trial procedures and requirements;

- Age >18 and < 80 years;

- Ability to understand, and willingness to sign, informed consent.