We report on the immunogenicity and clinical effects in a phase I/II dose escalation trial of a DNA fusion vaccine in patients with prostate cancer. The vaccine encodes a domain (DOM) from fragment C of tetanus toxin linked to an HLA-A2-binding epitope from prostate-specific membrane antigen (PSMA), PSMA(27-35). We evaluated the effect of intramuscular vaccination without or with electroporation (EP) on vaccine potency. Thirty-two HLA-A2(+) patients were vaccinated and monitored for immune and clinical responses for a follow-up period of 72 weeks. At week 24, cross-over to the immunologically more effective delivery modality was permitted; this was shown to be with EP based on early antibody data, and subsequently, 13/15 patients crossed to the +EP arm. Thirty-two HLA-A2(-) control patients were assessed for time to next treatment and overall survival. Vaccination was safe and well tolerated. The vaccine induced DOM-specific CD4(+) and PSMA(27)-specific CD8(+) T cells, which were detectable at significant levels above baseline at the end of the study (p = 0.0223 and p = 0.00248, respectively). Of 30 patients, 29 had a measurable CD4(+) T-cell response and PSMA(27)-specific CD8(+) T cells were detected in 16/30 patients, with or without EP. At week 24, before cross-over, both delivery methods led to increased CD4(+) and CD8(+) vaccine-specific T cells with a trend to a greater effect with EP. PSA doubling time increased significantly from 11.97 months pre-treatment to 16.82 months over the 72-week follow-up (p = 0.0417), with no clear differential effect of EP. The high frequency of immunological responses to DOM-PSMA(27) vaccination and the clinical effects are sufficiently promising to warrant further, randomized testing.