Heterotypic cellular and molecular interactions in the tumor microenvironment (TME) control cancer progression. Here, we show that CD1d-restricted invariant natural killer (iNKT) cells control prostate cancer (PCa) progression by sculpting the TME. In a mouse PCa model, iNKT cells restrained the pro-angiogenic and immunosuppressive capabilities of tumor-infiltrating immune cells by reducing pro-angiogenic TIE2+, M2-like macrophages (TEMs), and sustaining pro-inflammatory M1-like macrophages. iNKT cells directly contacted macrophages in the PCa stroma, and iNKT cell transfer into tumor-bearing mice abated TEMs, delaying tumor progression. iNKT cells modulated macrophages through the cooperative engagement of CD1d, Fas, and CD40, which promoted selective killing of M2-like and survival of M1-like macrophages. Human PCa aggressiveness associate with reduced intra-tumoral iNKT cells, increased TEMs, and expression of pro-angiogenic genes, underscoring the clinical significance of this crosstalk. Therefore, iNKT cells may control PCa through mechanisms involving differential macrophage modulation, which may be harnessed for therapeutically reprogramming the TME.