Primary and metastatic tumor growth induces host tissue responses that are believed to support tumor progression. Understanding the molecular changes within the tumor microenvironment during tumor progression may therefore be relevant not only for discovering potential therapeutic targets, but also for identifying putative molecular signatures that may improve tumor classification and predict clinical outcome. To selectively address stromal gene expression changes during cancer progression, we performed cDNA microarray analysis of laser-microdissected stromal cells derived from prostate intraepithelial neoplasia (PIN) and invasive cancer in a multistage model of prostate carcinogenesis. Human orthologs of genes identified in the stromal reaction to tumor progression in this mouse model were observed to be expressed in several human cancers, and to cluster prostate and breast cancer patients into groups with statistically different clinical outcomes. Univariate Cox analysis showed that overexpression of these genes is associated with shorter survival and recurrence-free periods. Taken together, our observations provide evidence that the expression signature of the stromal response to tumor invasion in a mouse tumor model can be used to probe human cancer, and to provide a powerful prognostic indicator for some of the most frequent human malignancies.