Increasing evidence indicates that tumor-stromal cell interactions have a crucial role in tumor initiation and progression. These interactions modify cellular compartments, leading to the co-evolution of tumor cells and their microenvironment. Although the importance of microenvironmental alterations in tumor development is recognized, the molecular mechanisms underlying these changes are only now beginning to be understood. Epigenetic and gene expression changes have consistently been reported in cancer-associated stromal cells and the influence of the host genotype on tumorigenesis is also well documented. However, the presence of clonally selected somatic genetic alterations within the tumor microenvironment has been controversial. A thorough understanding of the co-evolution of these two cellular compartments will require carefully executed molecular studies combined with mathematical modeling.