Most cancer immunotherapies under present investigation are based on the belief that cytotoxic T cells are the most important anti-tumoral immune cells, whereas intra-tumoral macrophages would rather play a pro-tumoral role. We have challenged this antagonistic point of view and searched for collaborative contributions by tumor-infiltrating T cells and macrophages, reminiscent of those observed in anti-infectious responses. We demonstrate that, in a model of therapeutic vaccination, cooperation between myeloid cells and T cells is indeed required for tumor rejection. Vaccination elicited an early rise of CD11b + myeloid cells that preceded and conditioned the intra-tumoral accumulation of CD8 + T cells. Conversely, CD8 + T cells and IFNγ production activated myeloid cells were required for tumor regression. A 4-fold reduction of CD8 + T cell infiltrate in CXCR3KO mice did not prevent tumor regression, whereas a reduction of tumor-infiltrating myeloid cells significantly interfered with vaccine efficiency. We show that macrophages from regressing tumors can kill tumor cells in two ways: phagocytosis and TNFα release. Altogether, our data suggest new strategies to improve the efficiency of cancer immunotherapies, by promoting intra-tumoral cooperation between macrophages and T cells.