Tumor-induced immunosuppression is one of the crucial mechanisms of tumor evasion of immune surveillance. It contributes greatly to the failure of cancer vaccines. Immature myeloid cells (ImCs) play an important role in tumor-induced immunosuppression. These cells accumulate in large numbers in tumor-bearing hosts and directly inhibit T-cell functions via various mechanisms. In this study, we tried to eliminate ImCs in an attempt to improve antitumor response. In vivo administration of all-trans-retinoic acid (ATRA) dramatically reduced the presence of ImCs in all tested tumor models. This effect was not because of a direct antitumor effect of ATRA or decreased production of growth factors by tumor cells. Experiments with adoptive transfer demonstrated that ATRA differentiated ImC in vivo into mature dendritic cells, macrophages, and granulocytes. Decreased presence of ImC in tumor-bearing mice noticeably improved CD4- and CD8-mediated tumor-specific immune response. Combination of ATRA with two different types of cancer vaccines in two different tumor models significantly prolonged the antitumor effect of the treatment. These data suggest that elimination of ImC with ATRA may open an opportunity to improve the effect of cancer vaccines.