Therapeutic cancer vaccines rely on the immune system to eliminate tumor cells. In contrast to chemotherapy or passive (adoptive) immunotherapies with antibodies or ex vivo-expanded T cells, therapeutic vaccines do not have a direct anti-tumor activity, but aim to reset patients' immune systems to achieve this goal. Recent identification of effective ways of enhancing immunogenicity of tumor-associated antigens, including the use of dendritic cells and other potent vectors of cancer vaccines, provide effective tools to induce high numbers of circulating tumor-specific T cells. However, despite indications that some of the new cancer vaccines may be able to delay tumor recurrence or prolong the survival of cancer patients, their ability to induce cancer regression remains low. Recent reports help to identify and prospectively remove the remaining obstacles towards effective therapeutic vaccination of cancer patients. They indicate that the successful induction of tumor-specific T cells by cancer vaccines is not necessarily associated with the induction of functional cytotoxic T lymphocytes, and that current cancer vaccines may promote undesirable expansion of Treg cells. Furthermore, recent studies also identify the tools to counteract such phenomena, in order to assure the desirable induction of Th1-cytotoxic T lymphocytes, NK-mediated type-1 immunity and appropriate homing of effector cells to tumors.