Metastasis is a multi-step process in which direct crosstalk between cancer cells and their microenvironment plays a key role. Here, we assessed the effect of paired tumor-associated and normal lung tissue mesenchymal stem cells (MSCs) on the growth and dissemination of primary human lung carcinoma cells isolated from the same patients. We show that the tumor microenvironment modulates MSC gene expression and identify a four-gene MSC signature that is functionally implicated in promoting metastasis. We also demonstrate that tumor-associated MSCs induce the expression of genes associated with an aggressive phenotype in primary lung cancer cells and selectively promote their dissemination rather than local growth. Our observations provide insight into mechanisms by which the stroma promotes lung cancer metastasis.