Reciprocal interactions between tumor and stromal cells propel cancer progression and metastasis. A complete understanding of the complex contributions of the tumor stroma to cancer progression necessitates a careful examination of the extracellular matrix (ECM), which is largely synthesized and modulated by cancer-associated fibroblasts. This structurally supportive meshwork serves as a signaling scaffold for a myriad of biologic processes and responses favoring tumor progression. The ECM is a repository for growth factors and cytokines that promote tumor growth, proliferation, and metastasis through diverse interactions with soluble and insoluble ECM components. Growth factors activated by proteases are involved in the initiation of cell signaling pathways essential to invasion and survival. Various transmembrane proteins produced by the cancer stroma bind the collagen and fibronectin-rich matrix to induce proliferation, adhesion, and migration of cancer cells, as well as protease activation. Integrins are critical liaisons between tumor cells and the surrounding stroma, and with their mechano-sensing ability, induce cell signaling pathways associated with contractility and migration. Proteoglycans also bind and interact with various matrix proteins in the tumor microenvironment to promote cancer progression. Together, these components function to mediate cross-talk between tumor cells and fibroblasts ultimately to promote tumor survival and metastasis. These stromal factors, which may be expressed differentially according to cancer stage, have prognostic utility and potential. This review examines changes in the ECM of cancer-associated fibroblasts induced through carcinogenesis, and the impact of these changes on cancer progression. The implication is that cancer progression, even in epithelial cancers, may be based in large part on changes in signaling from cancer-associated stromal cells. These changes may provide early prognostic indicators to further stratify patients during treatment or alter the timing of their follow-up visits and observations.