Combination Immunotherapy in Biochemically Recurrent Prostate Cancer

* For Safety Lead-in * 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 upper limit of normal (ULN) (OR in participants with Gilbert's syndrome, a total bilirubin less than or equal to 3.0), aspartate aminotransferase (AST) and alanine aminotransferase (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 (rilimogene galvacirepvec/rilimogene glafolivec) and CV301 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 * For Biochemical Recurrence: * Prostate-specific antigen (PSA) progression defined by sequence of rising values separated by \>1 week (2 separate increasing values over a minimum of 2ng/ml (Prostate Cancer Working Group 2 (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 * Eastern Cooperative Oncology Group (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 * Hemoglobin (Hgb) greater than or equal to 9 g/dL * Prothrombin time (PT) less than or equal to 1.5 x ULN * Activated partial thromboplastin time (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 Radiation Therapy Oncology Group (RTOG) -American Society for Therapeutic Radiation Oncology (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 computed tomography (CT) scan/magnetic resonance imaging (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 central nervous system (CNS), heart, lungs, kidneys, skin, and gastrointestinal (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 participants 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 Antigen direct immunotherapy's (e.g., vaccinia Antigen direct immunotherapy) * 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 * 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 hepatitis B virus (HBV) or hepatitis C virus (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 (systolic blood pressure (SBP)\>170/diastolic blood pressure (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.