Inclusion Criteria

- INCLUSION CRITERIA:

A. Histopathological documentation of prostate cancer confirmed in the Laboratory of
Pathology at: NIH Clinical Center, National Institutes of Health (NIH), the National Naval
Medical Center, or Walter Reed Army Medical Center prior to starting this study. If no
pathologic specimen is available, patients may enroll with a pathologist's report showing
a histologic diagnosis of prostate cancer and a clinical course consistent with the
disease.

B. Must have either a) biopsy proven, locally recurrent prostate cancer following local
radiation or cyrotherapy as defined by the ASTRO consensus criteria as 3 consecutively
rising PSA levels or b) have refused or not be candidates for local definitive therapy
(surgery or radiation therapy) and have clinically progressive disease on androgen
deprivation therapy (e.g., three increases in PSA over nadir, separated by at least one
week). For patients with previous RT, the biopsy confirming local recurrence must be done
at least 18 months after the completion of RT.

Since this may also generate a systemic immune response, patients with minimal
extraprostatic disease may be enrolled.

C. Agree to use adequate contraception prior to study entry and for at least 4 months
following the last vaccine injection.

D. Life expectancy greater than or equal to 6 months.

E. ECOG performance status of 0 to 2 (see Appendix A).

F. Recovered from any acute toxicity related to prior therapy, including surgery, and
radiation (treatment must have been completed at least 4 weeks prior to being eligible for
the study).

G. Hematological eligibility parameters (within 16 days of starting therapy, see Appendix
D).

Granulocyte count greater than or equal to 1,500/mm3

Platelet count greater than or equal to 100,000/mm3

Lymphocyte count greater than or equal to 500/mm3

Hgb greater than or equal to 10 Gm/dL

H. Biochemical eligibility parameters (within 16 days of starting therapy):

-A 24-hour urine collection for baseline to measure creatinine clearance, protein and
electrolytes. CrCl greater than 60mL/min, proteinuria less than 1000 milligrams per 24
hours, and no abnormal sediment. Serum creatinine not above normal limits OR creatinine
clearance on a 24 hour urine collection of greater than 60 mL/min. For patients who are
not able to obtain an accurate collection, a calculated creatinine clearance and urine
analysis for protein may be used. Any abnormalities in the sediment or the presence of
hematuria without a likely underlying cause should prompt the investigator to consider an
evaluation by a nephrologist or urologist for evidence of underlying renal pathology.

Patients may be eligible if the underlying cause of the abnormality is determined to be
non-renal.

-Hepatic function: Bilirubin equal to 1.5 mg/dL or patients with Gilbert's syndrome, a
total bilirubin less than or equal to 3.0 mg/dL, AST and ALT less than 2.5 times upper
limit of normal.

I. No other active malignancies within the past 12 months (with the exception of
non-melanoma skin cancers or carcinoma in situ of the bladder) or life threatening
illnesses.

J. Willing to travel to the NIH for follow-up visits.

K. 18 years of age or greater.

L. Vaccinia-naive or vaccinia immune.

M. Able to understand and sign informed consent.

N. Tested for HLA-A2; however, the results of this test will not affect entry into this
study. This test may be drawn by the patient's referring physician at the time of
referral (see Screening Consent for HLA typing). This consent will be mailed to the
patient and discussed with patient. The signed consent will be signed with a non-family
member witness and then mailed to the assigned research nurse at the NIH Clinical Center.

O. Concurrent hormonal therapy will be allowed.

P. PT / PTT will be drawn prior to any invasive protocol related procedure (i.e., prostate
biopsy or intraprostatic injection) and standard clinical guidelines followed.

EXCLUSION CRITERIA:

A. Patients should have no evidence of being immunocompromised as listed below.

- Human immunodeficiency virus positivity due to the potential for decreased tolerance
and may be at risk for severe side effects.

- Active autoimmune diseases such as, Addison's disease, Hashimoto's thyroiditis, or
systemic lupus erythematous, Sjogren syndrome, scleroderma, myasthenia gravis,
Goodpasture syndrome active Grave's disease. Patients with a history of autoimmunity
that has not required systemic immunosuppressive therapy or does not threaten vital
organ function including CNS, heart, lungs, kidneys, skin, and GI tract will be
allowed.

- Hepatitis B or C positivity.

- Concurrent use of systemic steroids, except for physiologic doses for systemic
steroid replacement or local (topical, nasal, or inhaled) steroid use. Steroid eye
drops are contraindicated for at least 2 weeks prior vaccinia vaccination and at
least 4 weeks post vaccinia vaccination.

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

C. Must be able to avoid close household contact (close household contacts are those who
share housing or have close physical contact) for at least three weeks after recombinant
vaccinia vaccination with persons with active or a history of eczema or other eczematoid
skin disorders; those with other acute, chronic or exfoliative skin conditions (e.g.,
atopic dermatitis, burns, impetigo, varicella zoster, severe acne, 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), including
HIV infection.

D. Serious intercurrent medical illness which would interfere with the ability of the
patient to carry out the treatment program, including, but not limited to, inflammatory
bowel disease, Crohn's disease, ulcerative colitis, or active diverticulitis.

E. Patients with cardiac disease that have fatigue, palpitation, dyspnea or angina with
ordinary physical activity (New York Heart Association class 2 or greater) are not
eligible.

F. Patients who have objective evidence of congestive heart failure by physical exam or
imaging are not eligible.

G. Patients with pulmonary disease that have fatigue or dyspnea with ordinary physical
activity are not eligible.

H. Concurrent chemotherapy.

I. Clinically active brain metastasis, or with a history of seizures, encephalitis, or
multiple sclerosis.

J. Serious hypersensitivity reaction to egg products.