Innate immune cells can constitute a substantial proportion of the cells within the tumor microenvironment and have been associated with tumor malignancy in patients and animal models of cancer; however, the mechanisms by which they modulate cancer progression are incompletely understood. Here, we show that high levels of cathepsin protease activity are induced in the majority of macrophages in the microenvironment of pancreatic islet cancers, mammary tumors, and lung metastases during malignant progression. We further show that tumor-associated macrophage (TAM)-supplied cathepsins B and S are critical for promoting pancreatic tumor growth, angiogenesis, and invasion in vivo, and markedly enhance the invasiveness of cancer cells in culture. Finally, we demonstrate that interleukin-4 (IL-4) is responsible for inducing cathepsin activity in macrophages in vitro and in vivo. Together, these data establish IL-4 as an important regulator, and cathepsin proteases as critical mediators, of the cancer-promoting functions of TAMs.