Macrophages are primary cells of the innate immune system that mediate tumor progression. However, the motile behavior of macrophages and interactions with tumor cells are not well understood. Here, we exploit the optical transparency of larval zebrafish and perform real-time imaging of macrophage-melanoma interactions. We found that macrophages are highly motile in the tumor microenvironment. Macrophages extend dynamic projections between tumor cells that precede invasive melanoma migration. Modulating macrophage motility with a dominant inhibitory mutation in Rac2 inhibits recruitment to the tumor and impairs tumor invasion. However, a hyperactivating mutation in Rac2 does not affect macrophage recruitment but limits macrophage projections into the melanoma mass and reduces invasive melanoma cell migration. Taken together, these findings reveal a role for Rac2-mediated macrophage protrusive motility in melanoma invasion.