Recent molecular classifications of colorectal cancer (CRC) based on global gene expression profiles have defined subtypes displaying resistance to therapy and poor prognosis. Upon evaluation of these classification systems, we discovered that their predictive power arises from genes expressed by stromal cells rather than epithelial tumor cells. Bioinformatic and immunohistochemical analyses identify stromal markers that associate robustly with disease relapse across the various classifications. Functional studies indicate that cancer-associated fibroblasts (CAFs) increase the frequency of tumor-initiating cells, an effect that is dramatically enhanced by transforming growth factor (TGF)-β signaling. Likewise, we find that all poor-prognosis CRC subtypes share a gene program induced by TGF-β in tumor stromal cells. Using patient-derived tumor organoids and xenografts, we show that the use of TGF-β signaling inhibitors to block the cross-talk between cancer cells and the microenvironment halts disease progression.