In order to metastasize, cancer cells need to acquire a motile phenotype. Previously, development of this phenotype was thought to rely on the acquisition of selected, random mutations and thus would occur late in cancer progression. However, recent studies show that cancer cells disseminate early, implying the existence of a different, faster route to the metastatic motile phenotype. Using a spontaneous murine model of melanoma, we show that a subset of bone marrow-derived immune cells (myeloid-derived suppressor cells or MDSC) preferentially infiltrates the primary tumor and actively promotes cancer cell dissemination by inducing epithelial-mesenchymal transition (EMT). CXCL5 is the main chemokine attracting MDSC to the primary tumor. In vitro assay using purified MDSC showed that TGF-β, EGF, and HGF signaling pathways are all used by MDSC to induce EMT in cancer cells. These findings explain how cancer cells acquire a motile phenotype so early and provide a mechanistic explanation for the long recognized link between inflammation and cancer progression.