Background: Immunotherapy could potentially prevent disease progression for early-stage prostate cancer. In this randomized Phase 2 clinical trial, we evaluated the clinical effects of PROSTVAC, a vaccinia/fowlpox viral vector-based immunotherapy that contains PSA and three T-cell costimulatory molecules, in patients with localized prostate cancer. Methods:154 patients with clinically localized, low- or favorable intermediate-risk prostate cancer active surveillance were randomized (2:1) to receive 7 doses of subcutaneous PROSTVAC or placebo (empty fowlpox vector) over 140 days. Post-intervention prostate biopsy was performed 7-14 days after the last dose. Participants were followed for 6 months post-treatment. The primary outcome was change from baseline to post-vaccination in CD4 and CD8 T cell infiltration in biopsy tumor tissue. Secondary outcomes included changes in prostate biopsy Gleason grade (Grade Group) and serum PSA. Results: There were no differences in CD4 and CD8 densities (count of cells/mm²) in post-treatment biopsy tumor tissue between groups (p = 0.63 and p = 0.75, respectively). Compared to placebo, patients who received PROSTVAC were less likely to demonstrate upgrading at follow-up biopsy, but this difference did not attain significance (22% vs. 40%, p= 0.08). There was no difference in the change of PSA from baseline to 6 months post-treatment between arms (p= 0.30). Conclusions: In this first-of-kind trial of immunotherapy for localized prostate cancer, PROSTVAC was well tolerated but did not elicit significant prostate tissue T-cell responses compared to placebo. The favorable post-treatment biopsy grade findings in PROSTVAC patients merit further evaluation and longer-term clinical follow-up. Clinical trial information: NCT02326805.