Abstract Background Immunotherapies have demonstrated clinical benefit for many types of cancers, however many patients do not respond, and treatment-related adverse effects can be severe. Hence many efforts are underway to identify treatment predictive biomarkers. We have reported the results of two phase I trials using a DNA vaccine encoding prostatic acid phosphatase (PAP) in patients with biochemically recurrent prostate cancer. In both trials, persistent PAP-specific Th1 immunity developed in some patients, and this was associated with favorable changes in serum PSA kinetics. In the current study, we sought to determine if measures of antigen-specific or antigen non-specific immunity were present prior to treatment, and associated with subsequent immune response, to identify possible predictive immune biomarkers. Methods Patients who developed persistent PAP-specific, IFNγ-secreting immune responses were defined as immune “responders.” The frequency of peripheral T cell and B cell lymphocytes, natural killer cells, monocytes, dendritic cells, myeloid derived suppressor cells, and regulatory T cells were assessed by flow cytometry and clinical laboratory values. PAP-specific immune responses were evaluated by cytokine secretion in vitro, and by antigen-specific suppression of delayed-type hypersensitivity to a recall antigen in an in vivo SCID mouse model. Results The frequency of peripheral blood cell types did not differ between the immune responder and non-responder groups. Non-responder patients tended to have higher PAP-specific IL-10 production pre-vaccination (p = 0.09). Responder patients had greater preexisting PAP-specific bystander regulatory responses that suppressed DTH to a recall antigen (p = 0.016). Conclusions While our study population was small (n = 38), these results suggest that different measures of antigen-specific tolerance or regulation might help predict immunological outcome from DNA vaccination. These will be prospectively evaluated in an ongoing randomized, phase II trial.