DNA vaccines offer many advantages over other anti-tumor vaccine approaches due to their simplicity, ease of manufacturing, and safety. Results from several clinical trials in patients with cancer have demonstrated that DNA vaccines are safe and can elicit immune responses. However, to date few DNA vaccines have progressed beyond phase I clinical trial evaluation. Studies into the mechanism of action of DNA vaccines in terms of antigen-presenting cell types able to directly present or cross-present DNA-encoded antigens, and the activation of innate immune responses due to DNA itself, have suggested opportunities to increase the immunogenicity of these vaccines. In addition, studies into the mechanisms of tumor resistance to anti-tumor vaccination have suggested combination approaches that can increase the anti-tumor effect of DNA vaccines. This review focuses on these mechanisms of action and mechanisms of resistance using DNA vaccines, and how this information is being used to improve the anti-tumor effect of DNA vaccines. These approaches are then specifically discussed in the context of human prostate cancer, a disease for which DNA vaccines have been and continue to be explored as treatments.