Tumor cells (over-) express specific antigens which allow them to be recognized and destroyed by the immune system. Triggering anti-tumor immunity in cancer patients by specific vaccination is foreseen as a safe and versatile method to control cancer. As a source of antigen, whole tumor cells, nucleic acids, proteins or derived peptides have been used. This review focuses on the utilization of vaccines based on plasmid DNA (pDNA) and messenger RNA (mRNA) coding for tumor associated antigens. Both vectors (pDNA and mRNA) are grouped under the designation "minimal nucleic acid vector" or MNAV. The current knowledge on anti-tumor vaccination based on MNAV-encoded tumor antigens, methods of delivery, principles of production and optimization is discussed. Furthermore, an up-to-date summary of published clinical trials using MNAV for the vaccination against solid tumors is given. Recent preclinical and early phase clinical trials demonstrate promising synergies between vaccination and other treatments such as chemotherapy or non-specific immune enhancement regimens. Combining optimized MNAV formulations and parallel adjuvant treatments could allow to turn MNAV-based vaccines into efficient anti-tumor immunotherapies in humans.