Tumor relapse after chemotherapy-induced regression is a major clinical problem, because it often involves inoperable metastatic disease. Tumor-associated macrophages (TAM) are known to limit the cytotoxic effects of chemotherapy in preclinical models of cancer. Here, we report that an alternatively activated (M2) subpopulation of TAMs (MRC1(+)TIE2(Hi)CXCR4(Hi)) accumulate around blood vessels in tumors after chemotherapy, where they promote tumor revascularization and relapse, in part, via VEGF-A release. A similar perivascular, M2-related TAM subset was present in human breast carcinomas and bone metastases after chemotherapy. Although a small proportion of M2 TAMs were also present in hypoxic tumor areas, when we genetically ablated their ability to respond to hypoxia via hypoxia-inducible factors 1 and 2, tumor relapse was unaffected. TAMs were the predominant cells expressing immunoreactive CXCR4 in chemotherapy-treated mouse tumors, with the highest levels expressed by MRC1(+) TAMs clustering around the tumor vasculature. Furthermore, the primary CXCR4 ligand, CXCL12, was upregulated in these perivascular sites after chemotherapy, where it was selectively chemotactic for MRC1(+) TAMs. Interestingly, HMOX-1, a marker of oxidative stress, was also upregulated in perivascular areas after chemotherapy. This enzyme generates carbon monoxide from the breakdown of heme, a gas known to upregulate CXCL12. Finally, pharmacologic blockade of CXCR4 selectively reduced M2-related TAMs after chemotherapy, especially those in direct contact with blood vessels, thereby reducing tumor revascularization and regrowth. Our studies rationalize a strategy to leverage chemotherapeutic efficacy by selectively targeting this perivascular, relapse-promoting M2-related TAM cell population.