Inclusion Criteria

- INCLUSION CRITERIA:

A. Histopathological documentation of prostate cancer confirmed in the Laboratory of
Pathology at the: 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 metastatic androgen insensitive prostate cancer with no bone pain requiring
narcotics and have had no prior chemotherapy.

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

D. ECOG performance status of 0-1.

E. No systemic steroid or steroid eye drop use within 2 weeks prior to initiation of
experimental therapy.

F. Hematological eligibility parameters

- Granulocyte count greater than or equal to1,500/mm(3)

- Platelet count greater than or equal to100,000/mm(3)

- Hgb greater than or equal to 9 Gm/dL

- Lymphocyte count greater than or equal to 500/mm(3).

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

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

H. 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.

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

J. 18 years of age or greater.

K. Vaccinia-naive or vaccinia immune.

L. Able to understand and sign informed consent.

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

N. Patients must remain on medical castration therapy, unless they have had surgical
castration

O. Patients must have recovered from acute toxicities related to prior therapy or surgery.
For chemotherapy typically this is 3-4 weeks.

P. Parameters for assessment of baseline renal function:

- Serum creatinine not above the institution limits of normal, OR creatinine clearance
on a 24 hour urine collection of greater than or equal to 60 mL/min.

- Patients must have less than grade 2 proteinuria (unless the cause is determined not
to be renal.)

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.

- Hepatitis B or C positivity

- Concurrent use of topical steroids (including steroid eye drops) or systemic
steroids. Nasal or inhaled steroid use is permitted

B.Patients should have no autoimmune diseases that have required treatment such as,
Addison's disease, Hashimoto's thyroiditis, or systemic lupus erythematous, Sjogren
syndrome, scleroderma, Goodpasture syndrome, and active Grave's disease. Also excluded
are patients with autoimmune hemolytic anemia, ulcerative and hemorrhagic colitis,
endocrine disorders (e.g., thyroiditis, hyperthyroidism, hypothyroidism, autoimmune
hypophysitis/hypopituitarism, and adrenal insufficiency), sarcoid granuloma, myasthenia
gravis, polymyositis, and Guillain-Barre syndrome. 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.

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

D. Do not administer the recombinant vaccinia vaccine if the recipient, or for at least
three weeks after vaccination, their close household contacts (close household contacts
are those who share housing or have close physical contact) are: 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.

E. Serious intercurrent medical illness (e.g., one that requires treatment) 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.

F. 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.

G. Patients with a history of congestive heart failure or who have objective evidence of
congestive heart failure by physical exam or imaging are not eligible.

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

I. Concurrent chemotherapy.

J. No brain metastasis, or with a history of seizures, encephalitis, or multiple
sclerosis.

K. Serious hypersensitivity reaction to egg products.

L. Prior splenectomy.

M. Patients who have received prior MDX-01.