Tumor-derived exosomes are emerging as mediators of tumorigenesis with a tissue-specific address and message. We explored the function of melanoma-derived exosomes in formation of primary tumors and metastatic progression in both murine models and patients. Whereas exosomes from highly metastatic melanoma cells increased the metastatic behavior of primary tumor cells by ‘educating’ bone marrow (BM) progenitor cells via the MET receptor, exosomes from low metastatic melanoma cells did not alter the incidence of metastases. Melanoma-derived exosomes induced vascular leakiness at pre-metastatic sites, and reprogrammed BM progenitor cells towards a pro-vasculogenic phenotype (c-Kit+Tie2+MET+). Reducing MET expression in tumor-derived exosomes diminished the pro-metastatic behavior of BM cells. Importantly, MET expression was upregulated in circulating BM progenitor cells (CD45-CD117low and CD45-CD117lowTIE2+) isolated from stage III and stage IV melanoma patients. Rab1a, Rab5b, Rab7, and Rab27a were highly expressed in melanoma and Rab27a RNA interference decreased exosome production and/or soluble angiogenic factors in melanoma cells, thereby preventing mobilization of BM progenitor cells, tumor growth and metastasis. Finally, we identified a ‘melanoma signature’ in exosomes isolated from metastatic melanoma patients, comprised of TYRP2, VLA-4, Hsp70, an Hsp90 isoform and MET oncoprotein, which together with Rab proteins, appear to represent exosome-specific proteins with prognostic potential, and may provide new therapeutic targets.