A Phase II Study of PROSTVAC-V (Vaccinia)/TRICOM and PROSTVAC-F (Fowlpox)/TRICOM With GM-CSF in Patients With PSA Progression After Local Therapy for Prostate Cancer

Inclusion Criteria: * Patients with histologically proven prostate cancer and tumors limited to the prostate (including seminal vesical involvement, provided all visible disease was surgically removed) that have completed local therapy and have an elevated PSA after surgery or rising PSA after radiation therapy, as defined below; patients with lymph node involvement (D1) are not eligible * Histologically confirmed diagnosis of prostate cancer * Previous treatment with definitive surgery or radiation therapy or both * No evidence of metastatic disease on physical exam, CT (MRI), and bone scan within 4 weeks prior to randomization * Prior neoadjuvant/adjuvant hormonal or chemotherapy is allowed if it was last used \>= 1 year prior to enrollment (no prior vaccine/immunotherapy for prostate cancer will be allowed) * No therapy modulating testosterone levels (such as leuteinizing-hormone releasing-hormone agonists/antagonists and antiandrogens) is permitted within 1 year prior to enrollment; agents such as 5-reductase inhibitors, ketoconazole, megestrol acetate, systemic steroids, and herbal products are not permitted at any time during the period that the PSA values are being collected * Hormone-sensitive prostate cancer as evident by a serum total testosterone level \> 150 ng/dL at the time of enrollment within 4 weeks prior to randomization * There must be one PSA measurement (referred to as the baseline PSA) obtained within one week prior to registration; the baseline PSA value must be greater than 0.4 ng/mL (after prostatectomy) or greater than 1.5 ng/mL (after radiation therapy) * All patients must have evidence of biochemical progression as determined by 3 PSA measurements (PSA1, PSA2, PSA3), each higher than the previous value, each obtained at least 4 weeks apart from the others with the most recent one (PSA3) being the baseline PSA; all of these PSA values must be obtained at the same reference lab; the earliest (PSA1) must be done within 6 months prior to registration. * PSA doubling time (PSADT) must be less than 12 months, calculated using the following formula: PSADT in days = (0.693 (t))/(In (PSA3) - In (PSA2)) Where t = the number of days between PSA3 and PSA2 In = the natural log PSADT in months = PSADT in days divided by 30.4375 * Eastern Cooperative Oncology Group (ECOG) Performance Status 0 - 1 * Leukocytes \>= 3000/mm\^³ * Granulocytes \>= 1500/mm\^3 * Platelet count \>= 100,000/mm\^3 * Serum creatinine within normal institutional limits or creatinine clearance \>= 60 mL/min for patients with creatinine levels above institutional normal (a calculated clearance may be used); an initial urine analysis will be required with grade 0 proteinuria and no abnormal sediment; for any positive protein a 24 hour urine should be less than 1,000 mg per 24 hours and no indication of chronic renal disease * Serum total bilirubin, and alkaline phosphatase within normal institutional limits * SGOT (AST) and SGPT (ALT) =\< 2.5 x institutional upper limit of normal * Patients cannot have evidence of immunosuppression: * Patients must be human immunodeficiency virus sero-negative due to the potential for severe reactions to vaccinia and the need for an intact immune system to respond to the immunization * Patients must not have active autoimmune diseases such as Addison's disease, Hashimoto's thyroiditis, systemic lupus erythematous, Sjogren syndrome, scleroderma, myasthenia gravis, Goodpasture syndrome or active Grave's disease; patients with a history of autoimmunity that has required systemic immunosuppressive therapy or has impaired organ function including CNS, heart, lungs, kidneys, skin, and GI tract are ineligible; patients receiving replacement thyroid hormone would be eligible * No concurrent use of systemic steroids, except for local (topical, nasal, or inhaled) steroid use; steroid eye drops are contraindicated for at least 2 weeks before vaccinia vaccination and at least 4 weeks post vaccinia vaccination * Patients must be hepatitis B and hepatitis C negative * Patients must have a normal PT/INR within 4 weeks prior to randomization * Patients must not be receiving any other investigational agents or receiving concurrent anticancer therapy * No uncontrolled intercurrent illness including, but not limited to, ongoing or active infection, symptomatic congestive heart failure, unstable angina pectoris, cardiac arrhythmia, or psychiatric illness/social situations that would limit compliance with study requirements; because of the recently recognized risk of cardiac inflammation after vaccinia, patients with clinically significant cardiomyopathy are excluded; patients must have recovered from any intercurrent illness and any acute toxicity related to prior therapy (i.e., surgery and/or radiation) * Patients must use a safe and effective method of contraception to prevent virus transmission; the potential risk to spermatogenesis and fetal development after paternal immunization with this vaccine is not known; patients must agree to avoid fathering a child and use a latex barrier with adequate contraception prior to study entry and for at least 4 months following the last vaccine injection * All sites of disease must be evaluated within 4 weeks prior to registration * Patients with significant allergy or hypersensitivity to eggs should be excluded; patients must not have a history of allergy or untoward reaction to prior vaccination with vaccinia virus or to any component of the vaccinia vaccine regimen * Patients must not have active eczema, a history of eczema, atopic dermatitis, or Darier.s disease; other acute, chronic, or exfoliative skin conditions (e.g., burns, impetigo, varicella zoster, severe acne, contact dermatitis, psoriasis, herpes or other open rashes or wounds * Patients must be able to avoid close contact with those who share housing or have close physical contact for at least three weeks after recombinant vaccinia vaccination with persons at increased risk including those with active or a history of eczema or atopic dermatitis, or Darier"s disease; those with other acute, chronic or exfoliative skin conditions (e.g., burns, impetigo, varicella zoster, severe acne, contact dermatitis, psoriasis, herpes or other open rashes or wounds) until condition resolves; pregnant or nursing women; children 3 years of age and under; and immunodeficient or immunosuppressed persons (by disease or therapy), which includes those infected with HIV until the condition resolves