Metastasis depends on the ability of tumor cells to establish a relationship with the newly seeded tissue that is conducive to their survival and proliferation. However, the factors that render tissues permissive for metastatic tumor growth have yet to be fully elucidated. Breast tumors arising during pregnancy display early metastatic proclivity, raising the possibility that pregnancy may constitute a physiological condition of permissiveness for tumor dissemination. Here we have shown that during murine gestation, metastasis is enhanced regardless of tumor type, and that decreased NK cell activity is responsible for the observed increase in experimental metastasis. Gene expression changes in pregnant mouse lung and liver were shown to be similar to those detected in premetastatic sites and indicative of myeloid cell infiltration. Indeed, myeloid-derived suppressor cells (MDSCs) accumulated in pregnant mice and exerted an inhibitory effect on NK cell activity, providing a candidate mechanism for the enhanced metastatic tumor growth observed in gestant mice. Although the functions of MDSCs are not yet understood in the context of pregnancy, our observations suggest that they may represent a shared mechanism of immune suppression occurring during gestation and tumor growth.