Heparanase is a β-D-endoglucuronidase that cleaves heparan sulfate, a complex glycosaminoglycan found ubiquitously throughout mammalian cells and tissues. Heparanase has been strongly associated with important pathological processes including inflammatory disease and tumor metastasis, through its ability to promote various cellular functions such as cell migration, invasion, adhesion, and cytokine release. A number of cell types express heparanase including leukocytes, cells of the vasculature as well as tumor cells. However, the relative contribution of heparanase from these different cell sources to these processes is poorly defined. It is now well-established that the immune system plays a critical role in shaping tumor progression. Intriguingly, leukocyte-derived heparanase has been shown to either assist or impede tumor progression, depending on the setting. This review covers our current knowledge of heparanase in immune regulation of tumor progression, as well as the potential applications and implications of exploiting or inhibiting heparanase in cancer therapy.