Inclusion Criteria:

- Histologically confirmed prostate cancer and tumors limited to the prostate

- Seminal vesical involvement allowed provided all visible disease has been
surgically removed

- Prior treatment with definitive surgery or radiation therapy or both

- At least 1 year since prior neoadjuvant/adjuvant chemotherapy or hormonal therapy

- More than 1 year since prior testosterone level-modulating therapy, such as LHRH
agonists/antagonists and antiandrogens

- Hormone-sensitive disease as evident by a serum total testosterone level > 150 ng/dL
within 4 weeks prior to registration

- Evidence of PSA progression after completion of definitive surgery and/or
radiotherapy, as demonstrated by all of the following:

- Three consecutively rising PSA values within the past 6 months, each obtained ≥
4 weeks apart

- Most recent PSA value > 0.4 ng/mL (after prostatectomy) OR > 1.5 ng/mL (after
radiotherapy)

- PSA doubling time < 12 months

- ECOG PS of 0-1

- Age of 18 and over

- WBC ≥ 3,000/mm^3

- Granulocyte count ≥ 1,500/mm^3

- Platelet count ≥ 100,000/mm^3

- Urine protein < 1,000 mg by 24-hour urine collection AND no evidence of chronic renal
disease (Creatinine normal or Creatinine clearance ≥ 60 mL/min)

- AST and ALT ≤ 2.5 times upper limit of normal

- Bilirubin normal

- Alkaline phosphatase normal

- Hepatitis B and hepatitis C negative

- PT/INR normal

- Human immunodeficiency virus sero-negative

- Recovered from prior therapy

- Patients must use a safe and effective method of contraception to prevent virus
transmission

- 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

- Recovered from any other illness

- Must be able to avoid close contact (i.e., shares the same house or has close
physical contact) with any of the following individuals for ≥ 3 weeks after treatment
with the study vaccinia vaccine:

- Individuals with a history of or active eczema, atopic dermatitis, Darier's
disease

- Individuals with other acute, chronic, or exfoliative skin condition, including
any of the following:

- Burns

- Impetigo

- Varicella zoster

- Severe acne

- Contact dermatitis

- Psoriasis

- Herpes

- Other open rashes or wounds

- Pregnant or nursing women

- Children ≤ 3 years of age

- Immunodeficient or immunosuppressed individuals either by disease or therapy,
including HIV-positive individuals

- Concurrent thyroid hormone-replacement therapy allowed

Exclusion Criteria:

- Lymph node involvement

- Metastatic disease by physical exam, CT scan, MRI, or bone scan within 4 weeks of
registration

- Prior vaccine therapy or immunotherapy for prostate cancer

- Administration of any of the following agents during the period in which the PSA
levels are collected:

- 5α-reductase inhibitors

- Ketoconazole

- Megestrol acetate

- Systemic steroids

- Herbal products

- Proteinuria or abnormal sediment by urine analysis

- Active autoimmune disease, including any of the following:

- Addison's disease

- Hashimoto's thyroiditis

- Systemic lupus erythematosus

- Sjögren's syndrome

- Scleroderma

- Myasthenia gravis

- Goodpasture's syndrome

- Active Graves' disease

- History of autoimmune disease that has required systemic immunosuppressive therapy or
has impaired central nervous system (CNS), heart, lung, kidney, skin, or
gastrointestinal tract function

- Concurrent systemic steroids

- Local (e.g., topical, nasal, inhaled) steroids allowed

- No steroid eye drops for ≥ 2 weeks before and ≥ 4 weeks after vaccinia
vaccination

- Receiving other investigational agents or concurrent anticancer therapy

- Uncontrolled intercurrent illness

- Symptomatic congestive heart failure

- Unstable angina pectoris

- Cardiac arrhythmia

- Psychiatric illness or social situation that would preclude study compliance

- Clinically significant cardiomyopathy

- Significant allergy or hypersensitivity to eggs

- History of allergy or untoward reaction to prior vaccination with vaccinia virus or
to any component of the study vaccinia vaccine regimen

- History of or active eczema

- Ongoing, active infection

- Atopic dermatitis

- Darier's disease

- Other acute, chronic, or exfoliative skin condition, including any of the following:

- Burns

- Impetigo

- Varicella zoster

- Severe acne

- Contact dermatitis

- Psoriasis

- Herpes

- Other open rashes or wounds