-  INCLUSION CRITERIA:

          -  Histopathological documentation of prostate cancer confirmed in either the Laboratory
             of Pathology at the National Institutes of Health (NIH) Clinical Center, or Walter
             Reed National Military Medical Center prior to enrollment. If no pathologic specimen
             is available, participants may enroll with a pathologist s report showing a histologic
             diagnosis of prostate cancer and a clinical course consistent with the disease.

          -  Recovery to baseline from acute toxicity related to prior therapy, including surgery
             and radiation. (28 days removed from last systemic therapy, 14 days removed from last
             radiation therapy).

          -  Hepatic function eligibility parameters (within 16 days before starting therapy):

             --Bilirubin less than or equal to ULN (OR in participants with Gilbert s syndrome, a
             total bilirubin less than or equal to 3.0), AST and ALT less than or equal to 1.5
             times upper limit of normal.

          -  Adequate renal function defined by an estimated creatinine clearance > 50 mL/min
             according to the Cockcroft-Gault formula or by measure of creatinine clearance from 24
             hour urine collection.

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

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

          -  18 years of age or older.

          -  Able to understand and sign informed consent.

          -  The effects Prostvac, CV301 and MSB0011359C on the developing human fetus are unknown.
             For this reason, men must agree to use highly effective contraception (that is,
             methods with a failure rate of less than 1% per year) prior to study entry, for the
             duration of study therapy and at least four months after the last treatment
             administration. Should a woman become pregnant or suspect she is pregnant while her
             partner is participating in this study, she should inform her treating physician
             immediately.

          -  Additional Inclusion Criteria Specific to Safety Lead-In Cohort

               -  Castrate testosterone level (<50ng/dl or 1.7nmol /L)

               -  Progressive disease at study entry defined as one or more of the following
                  criteria occurring in the setting of castrate levels of testosterone:

                    -  Radiographic progression defined as any new or enlarging bone lesions or
                       growing lymph node disease, consistent with prostate cancer

        OR

          -  PSA progression defined by sequence of rising values separated by >1 week (2 separate
             increasing values over a minimum of 2ng/ml (PCWG2 PSA eligibility criteria). If
             participants had been on flutamide, PSA progression is documented 4 weeks or more
             after withdrawal. For participants on bicalutamide or nilutamide disease progression
             is documented 6 or more weeks after withdrawal.

             --Participants must agree to continuation of androgen deprivation therapy (ADT) with a
             gonadotropin-releasing hormone agonist/antagonist or bilateral orchiectomy

          -  ECOG performance status of 0-2 (Karnofsky >80%).

          -  Hematological eligibility parameters (within 16 days before starting therapy):

          -  Granulocyte count greater than or equal to 1000/mm^3

          -  Platelet count greater than or equal to 100 000/mm^3

          -  Hgb greater than or equal to 9 g/dL

          -  PT less than or equal to 1.5 x ULN

          -  aPTT less than or equal to 1.5 x ULN

        Additional Inclusion Criteria Specific to Biochemical Recurrence Cohort

          -  Biochemical progression defined as follows:

               -  For participants following definitive radiation therapy: a rise in PSA of greater
                  than or equal to 2 ng/mL above the nadir (per RTOG-ASTRO consensus criteria)

               -  For participants following radical prostatectomy: rising PSA after surgical
                  procedure (participants must have a PSA greater than or equal to 0.8 ng/mL)

          -  Participants must have a rising PSA as confirmed by 3 values a minimum of 1 week apart
             over at least a 1 month period of time.

          -  Participants must have a PSA doubling time of 5-15 months.

          -  ECOG performance status of 0-1 (Karnofsky greater than or equal to 80%).

          -  Negative CT scan/MRI and bone scan for metastatic prostate cancer.

          -  Baseline testosterone greater than or equal to 100 ng/dl.

          -  PSA less than or equal to 30 ng/mL.

          -  Hematological eligibility parameters (within 16 days before starting therapy):

               -  Granulocyte count greater than or equal to 1000/mm3

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

               -  Hgb greater than or equal to 10 g/dL

        EXCLUSION CRITERIA:

          -  Immunocompromised status due to:

               -  Human immunodeficiency virus (HIV) positivity.

               -  Active autoimmune diseases such as Addison's disease, Hashimoto's thyroiditis,
                  systemic lupus erythematosus, Sjogren syndrome, scleroderma, myasthenia gravis,
                  Goodpasture syndrome or active Grave's disease.

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

                    -  Participants with diabetes type I, vitiligo, or alopecia are allowed.

               -  Other immunodeficiency diseases

               -  Splenectomy

          -  Receipt of any organ transplantation, including allogeneic stem-cell transplantation,
             but with the exception of transplants that do not require immunosuppression (e.g.
             corneal transplant, hair transplant).

          -  Chronic administration (defined as daily or every other day for continued use > 14
             days) of systemic corticosteroids within 28 days before the first planned dose of
             investigational therapy. Use of corticosteroids with minimal systemic absorption (e.g.
             inhaled steroids, nasal sprays, and topical agents) is allowed.

          -  Serious intercurrent medical illness that, in the judgment of the investigator, would
             interfere with participant s ability to carry out the treatment program.

          -  Other medications used for urinary symptoms including 5-alpha reductase inhibitors
             (finasteride and dutasteride) and alternative medications known to alter PSA (e.g.
             phytoestrogens and saw palmetto).

          -  History of prior chemotherapy (chemotherapy allowed for lead-in cohort in castration
             resistant disease.)

          -  History of prior immunotherapy within the last 3 years (immunotherapy allowed for
             lead-in cohort in castration resistant disease.)

          -  Receipt of an investigational agent within 28 days (or 56 days for an antibody-based
             therapy) before the first planned dose of study drugs.

          -  Major surgery within 4 weeks prior to enrollment

          -  History of allergic reactions attributed to compounds of similar chemical or biologic
             composition to poxviral vaccines (e.g., vaccinia vaccine)

          -  Previous serious adverse reactions to smallpox vaccination

          -  History of allergic reactions attributed to monoclonal antibodies (grade 3)

          -  Known allergy to eggs, egg products, aminoglycoside antibiotics (e.g. gentamicin or
             tobramycin).

          -  History of atopic dermatitis or active skin condition (acute, chronic, exfoliative)
             that disrupts the epidermis

          -  History of grade greater than or equal to 2 radiation proctitis

          -  Unable to avoid close contact or household contact with the following high-risk
             individuals for three weeks after the Day 1 vaccination: (a) children less than or
             equal to 3 years of age, (b) pregnant or nursing women, (c) individuals with prior or
             concurrent extensive eczema or other eczemoid skin disorders, or (d) immunocompromised
             individuals, such as those with HIV.

          -  Participants who test positive for HBV or HCV

          -  Clinically significant cardiovascular/cerebrovascular disease as follows: cerebral
             vascular accident/stroke (< 6 months prior to the first planned dose of study drugs),
             myocardial infarction (< 6 months prior to the first planned dose of study drugs),
             unstable angina, congestive heart failure (New York Heart Association Classification
             Class greater than or equal to II), serious cardiac arrhythmia, or uncontrolled
             hypertension (SBP>170/DBP>105).

          -  Participants who have received a red cell transfusion within 2 weeks prior to
             enrollment.

          -  Participants unwilling to accept blood products as medically indicated.

          -  Individual tumor lesion(s) in the liver or chest which are 10 cm or larger.

          -  In the opinion of the investigator the risk of bleeding outweighs the potential
             benefit with M7824. Note: participants with a history of bleeding diathesis or recent
             (within 3 months) clinically significant bleeding events are also excluded.