Metastasis is a multistep process that requires acquisition of malignant cell phenotypes which allow tumor cells to escape from the primary tumor site. Each of the steps during metastatic progression involves co-evolution of the tumor and its microenvironment. Although tumor cells are the driving force of metastasis, new findings suggest that the host cells within the tumor microenvironment play a key role in influencing metastatic behavior. Many of these contributing cells are derived from the bone marrow; in particular, recruited bone marrow progenitor cells generate the “pre-metastatic niche” to which the tumor cells metastasize. Analysis of the molecular mechanisms involved in pre-metastatic niche formation has revealed that secreted soluble factors are key players in bone marrow cell mobilization during metastasis. In addition, membrane vesicles derived from both tumor and host cells have recently been recognized as new candidates with important roles in the promotion of tumor growth and metastasis. This review describes old ideas and presents new insights into the role of tumor and bone marrow-derived microvesicles and exosomes in pre-metastatic niche formation and metastasis.