Sequential Vaccinations in Prostate Cancer Patients

Background: * Adenocarcinoma of the prostate is the most common cancer diagnosis in American males and follows lung cancer as the leading cause of cancer death. * Vaccine strategies represent a novel therapeutic approach in the treatment for prostate cancer. One potential target for a prostate cancer vaccine is prostatic specific antigen (PSA), due to its restricted expression on prostate cancer and normal prostatic epithelial cells. Objectives: * The primary objective is to determine the impact of granulocyte-macrophage colony stimulating factor (GM-CSF) and recombinant fowlpox granulocyte-macrophage colony stimulating factor (rF-GM-CSF) on the immunologic response in patients treated with these vaccines. * Secondary - to determine the change in prostatic specific antigen (PSA)-specific T cells in patients treated with these vaccines using enzyme linked immunosorbent spot (ELISPOT) assay analysis. * To document any objective anti-tumor responses that may occur. Eligibility: * Patients must have androgen insensitive metastatic prostate cancer. * All patients will have received and progressed on hormonal therapy. * Must have objective evidence of metastasis or relapsing local disease. Therefore, must have a rising PSA and at least one of the following: positive bone scan, palpable disease, or positive imaging studies. * Must have a life expectancy of more than 6 months and the Eastern Cooperative Oncology Group (ECOG) status of 0 to 2. * Patients must be HLA-A2+. * Granulocyte count greater than or equal to 1,500/mm\^3, Platelet greater than or equal to 100,000/mm\^3, hemoglobin (Hgb) greater than or equal to 10Gm/dL, Lymphocyte count greater than or equal to 500/mm\^3; Bilirubin less than 1.5mg/dL, aspartate aminotransferase (AST) and alanine aminotransferase (ALT) less than 2.5x upper limit of normal (ULN),Creatinine Clearance greater than or equal to 60 * No significant cardiac disease, no significant pulmonary disease, no serious inter-current medical illness. Design: * Cohorts three, four and five will provide safety data combining cohort two with rGM-CSF as well as two doses of rFGM-CSF respectively. * This study will be conducted as a small, randomized pilot study to compare the immunologic effects of the above vaccine strategy alone, with recombinant GM-CSF, or with either of 2 doses of fowlpox-GM-CSF. * This study will consist of 4 randomized arms of 8 patients each, all of whom are HLA-A2+.