Therapeutic vaccination against cancer is an important approach which, when combined with other therapies, can improve long-term control of cancer. In fact, the induction of adaptive immune responses against Tumor Associated Antigens (TAAs) as well as innate immunity are important factors for tumor stabilization/eradication. A variety of immunization technologies have been explored in last decades and are currently under active evaluation, such as cell-based, protein, peptide and heat-shock protein-based cancer vaccines. Genetic vaccines are emerging as promising methodologies to elicit immune responses against a wide variety of antigens, including TAAs. Amongst these, Adenovirus (Ad)-based vectors show excellent immunogenicity profile and have achieved immunological proof of concept in humans. In vivo electroporation of plasmid DNA (DNA-EP) is also a desirable vaccine technology for cancer vaccines, as it is repeatable several times, a parameter required for the long-term maintenance of anti-tumor immunity. Recent findings show that combinations of different modalities of immunization (heterologous prime/boost) are able to induce superior immune reactions as compared to single-modality vaccines. In this review, we will discuss the challenges and requirements of emerging cancer vaccines, particularly focusing on the genetic cancer vaccines currently under active development and the promise shown by Ad and DNA-EP heterologous prime-boost.