The mechanisms by which a primary tumor affects a selected distant organ before tumor cell arrival remain to be elucidated. This report shows that Gr-1+CD11b+ cells are significantly increased in lungs of mice bearing mammary adenocarcinomas before tumor cell arrival. In the premetastatic lungs, these immature myeloid cells significantly decrease IFN-γ production and increase proinflammatory cytokines. In addition, they produce large quantities of matrix metalloproteinase 9 (MMP9) and promote vascular remodeling. Deletion of MMP9 normalizes aberrant vasculature in the premetastatic lung and diminishes lung metastasis. The production and activity of MMP9 is selectively restricted to lungs and organs with a large number of Gr-1+CD11b+ cells. Our work reveals a novel protumor mechanism for Gr-1+CD11b+ cells that changes the premetastatic lung into an inflammatory and proliferative environment, diminishes immune protection, and promotes metastasis through aberrant vasculature formation. Thus, inhibition of Gr-1+CD11b+ cells could normalize the premetastatic lung environment, improve host immunosurveillance, and inhibit tumor metastasis. Cancer Res; 70(15); 6139–49. ©2010 AACR.