A deeper understanding of the metastatic process is required for the development of new therapies that improve patient survival. Metastatic tumor cell growth and survival in distant organs is facilitated by the formation of a pre-metastatic niche that is composed of hematopoietic cells, stromal cells and extracellular matrix (ECM). Perivascular cells, including vascular smooth muscle cells (vSMCs) and pericytes, are involved in new vessel formation and in promoting stem cell maintenance and proliferation. Given the well-described plasticity of perivascular cells, we hypothesized that perivascular cells similarly regulate tumor cell fate at metastatic sites. We used perivascular-cell-specific and pericyte-specific lineage-tracing models to trace the fate of perivascular cells in the pre-metastatic and metastatic microenvironments. We show that perivascular cells lose the expression of traditional vSMC and pericyte markers in response to tumor-secreted factors and exhibit increased proliferation, migration and ECM synthesis. Increased expression of the pluripotency gene Klf4 in these phenotypically switched perivascular cells promoted a less differentiated state, characterized by enhanced ECM production, that established a pro-metastatic fibronectin-rich environment. Genetic inactivation of Klf4 in perivascular cells decreased formation of a pre-metastatic niche and metastasis. Our data revealed a previously unidentified role for perivascular cells in pre-metastatic niche formation and uncovered novel strategies for limiting metastasis.