Inclusion Criteria:  Written informed consent and HIPAA authorization for release of personal health information. NOTE: HIPAA authorization may be included in the informed consent or obtained separately. Age ≥ 18years at the time of consent. ECOG Performance Status of 0-1 within 28 days prior to registration. Histologically documented prostatic adenocarcinoma confirmed by a pathology report from prostate biopsy or a radical prostatectomy specimen. Previously undergone primary therapy for prostate cancer. Salvage external beam radiation or cryotherapy following primary therapy ≥ 6 months prior to randomization is allowed. Patients with low-risk biochemical recurrence, defined as a prostate specific antigen doubling time (PSADT) ≥10 months in patients who were previously treated with radical prostatectomy or radiation therapy  A rising PSA defined as the following  If the subject's primary therapy was radical prostatectomy (with or without adjuvant or salvage XRT), rising PSA is defined as 2 consecutive rising values above 0.2 ng/mL, each taken ≥ 3 weeks apart, and the last value ≥ 0.8 ng/mL If the subject received other primary therapies (e.g. XRT, cryosurgery, brachytherapy), rising PSA is defined per the Phoenix definition, i.e., 2 consecutive rising values above the PSA nadir plus 2.0 ng/mL. Testosterone ≥ 150 ng/dL ≤ 28 days of prior to registration  Adequate bone marrow, hepatic, and renal function:  ANC >1,500 cells/mm3 Hemoglobin >9.0 g/dL Platelet count >100,000 cells/mm3 Serum creatinine <2 × upper limit of normal (ULN) Serum total bilirubin <1.5 × ULN ALT <2.5 × ULN AST <2.5 × ULN Subject has baseline blood oxygen saturation on room air of ≥95% Subject is willing and able to provide an archived biopsy specimen which may be used for correlative studies and to determine HLA type; Subject with a female partner of child-bearing potential is eligible if he agrees to follow the contraceptive guidance, provided in the study, during the treatment period and for at least 120 days after the final dose of study treatment  Exclusion Criteria:  Patients with evaluable metastatic disease on bone or computed tomography (CT) or PET scans performed ≤8 weeks of registration (patients with PET scan findings consistent with metastasis but who have normal conventional imaging by CT/MRI/Bone scan using standard radiographic criteria ARE eligible) Patients with known brain metastases Patients with active autoimmune disease requiring systemic treatment within the past 3 months, a documented history of clinically severe autoimmune disease, or a disorder that requires systemic corticosteroids or immunosuppressive agents Patients with active infection requiring systemic therapy or is dependent on or currently receiving antibiotics that cannot be discontinued before dosing. (Note: Subjects who discontinue an antibiotic prior to dosing must wait at least 5 half-lives after the last dose of antibiotic before receiving any study treatment Subject has a contraindication (e.g., sensitivity/allergy) to trimethoprim/ sulfamethoxazole and ampicillin Subject has uncontrolled hypertension defined as systolic blood pressure >150 mmHg or diastolic pressure >90 mmHg, despite optimal medical management Subject has a history of listeriosis Subject has an implanted medical device that poses a high risk for bacterial colonization and/or that cannot be easily removed (e.g., prosthetic joints, artificial heart valves, pacemakers, orthopedic screws, metal plates, bone grafts, or other exogenous implants). NOTE: More common devices and prosthetics that include arterial and venous stents, dental and breast implants and venous access devices (e.g., Port-a-Cath or Mediport) are permitted. Sponsor must be contacted prior to consenting any subject who has any other device or implant