Inclusion Criteria:

- Patients with prostate cancer that is histologically confirmed.

- Patients must show biochemical progression after primary therapy, including surgery
or radiation (with or without neo-adjuvant androgen ablation). This detection of PSA
following treatment must occur within two years.

- Patients who have had intermittent hormonal treatment, following primary therapy, who
have non-castrate levels of testosterone (>50 ng/ml) are eligible. Hormonal status
will be recorded on the basis of serum testosterone levels.

- Karnofsky performance status >60%.

- Patients must have adequate organ function as defined by:

1. WBC > or = to 3500/mm3, platelet count > or = to 100,000 mm3.

2. Bilirubin <2.0 mg/100 ml or SGOT <3.0 X's the upper limit of normal.

3. Creatinine < or = to 2.0 mg/100 ml or creatinine clearance > or = to 40 cc/min.

- Patients must have recovered from the toxicity of any prior therapy, and not received
chemotherapy or radiation therapy for at least 4 weeks prior to entry into the trial.

- No history of an active secondary malignancy within the prior five years except for
nonmelanoma skin cancer. Patients with history of melanoma in situ will be permitted
since these lesions behave in a manner similar to compound nevi.

- Patients must be at least 18 years of age.

- Patients must sign informed consent.

Exclusion Criteria:

- Clinically significant cardiac disease (New York Heart Association Class III/IV), or
severe debilitating pulmonary disease.

- Radiographic evidence of metastatic disease.

- An infection requiring antibiotic treatment.

- Narcotic dependent pain.

- Anticipated survival of less than 6 months.

- Positive stool guaiac excluding hemorrhoids or history of documented radiation
induced proctitis.

- Allergy to seafood.

- Prior vaccine therapy at outside institution except for phase I monovalent trial
performed at MSKCC.