Hypoxia within a tumor acts as a strong selective pressure that promotes angiogenesis, invasion, and metastatic spread. In this study, we used immune competent bone marrow chimeric mice and syngeneic orthotopic mammary cancer models to show that hypoxia in the primary tumor promotes premetastatic niche formation in secondary organs. Injection of mice with cell-free conditioned medium derived from hypoxic mammary tumor cells resulted in increased bone marrow–derived cell infiltration into the lung in the absence of a primary tumor and led to increased metastatic burden in mammary and melanoma experimental metastasis models. By characterizing the composition of infiltrating bone marrow–derived cells, we identified CD11b⁺/Ly6C^med/Ly6G⁺ myeloid and CD3⁻/NK1.1⁺ immune cell lineages as key constituents of the premetastatic niche. Furthermore, the cytotoxicity of natural killer (NK) cells was significantly decreased, resulting in a reduced antitumor response that allowed metastasis formation in secondary organs to a similar extent as ablation of NK cells. In contrast, metastatic burden was decreased when active NK cells were present in premetastatic lungs. Together, our findings suggest that primary tumor hypoxia provides cytokines and growth factors capable of creating a premetastatic niche through recruitment of CD11b⁺/Ly6C^med/Ly6G⁺ myeloid cells and a reduction in the cytotoxic effector functions of NK cell populations. Cancer Res; 72(16); 3906–11. ©2012 AACR.