The emerging role of heparanase in tumor initiation, growth, metastasis, and chemoresistance is well recognized, encouraging the development of heparanase inhibitors as anticancer drugs. Unlike the function of heparanase in cancer cells, little attention has been given to heparanase contributed by cells composing the tumor microenvironment. Here, we focused on the cross-talk between macrophages, chemotherapy, and heparanase and the combined effect on tumor progression. Macrophages were markedly activated by chemotherapeutics paclitaxel and cisplatin, evidenced by increased expression of proinflammatory cytokines, supporting recent studies indicating that chemotherapy may promote rather than suppress tumor regrowth and spread. Strikingly, cytokine induction by chemotherapy was not observed in macrophages isolated from heparanase-knockout mice, suggesting macrophage activation by chemotherapy is heparanase dependent. paclitaxel-treated macrophages enhanced the growth of Lewis lung carcinoma tumors that was attenuated by a CXCR2 inhibitor. Mechanistically, paclitaxel and cisplatin activated methylation of histone H3 on lysine 4 (H3K4) in wild-type but not in heparanase-knockout macrophages. Furthermore, the H3K4 presenter WDR5 functioned as a molecular determinant that mediated cytokine induction by paclitaxel. This epigenetic, heparanase-dependent host-response mechanism adds a new perspective to the tumor-promoting functions of chemotherapy, and offers new treatment modalities to optimize chemotherapeutics.