Abstract The nature of the tumor microenvironment (TME) influences the ability of tumor-specific T cells to control tumor growth. In this study, we performed an unbiased comparison of the TME of regulatory T-cell (Treg)–replete and Treg-depleted carcinogen-induced tumors, including Treg-depleted responding (regressing) and non-responding (growing) tumors. This analysis revealed an inverse relationship between extracellular matrix (ECM) and T-cell infiltrates where responding tumors were T-cell rich and ECM poor, whereas the converse was observed in non-responder tumors. For this reason, we hypothesized that the ECM acted as a barrier to successful T-cell infiltration and tumor rejection. However, further experiments revealed that this was not the case but instead showed that an effective T-cell response dramatically altered the density of ECM in the TME. Along with loss of ECM and high numbers of infiltrating T cells, responder tumors were distinguished by the development of lymphatic and blood vessel networks with specialized immune function. ECM-rich tumors exhibited a stem cell–like gene expression profile and superior tumor-initiating capacity, whereas such features were absent in responder tumors. Overall, these findings define an extended role for an effective immune response, not just in direct killing of tumor cells but in widescale remodeling of the TME to favor loss of ECM, elimination of cancer stem cells, and propagation of adaptive immunity.