Emerging studies have begun to demonstrate that reprogrammed stromal cells play pivotal roles in tumor growth, metastasis, and resistance to therapy. However, the contribution of stromal cells to non-small-cell lung cancer (NSCLC) has remained underexplored. We used an orthotopic model of Kras-driven NSCLC to systematically dissect the contribution of specific hematopoietic stromal cells in lung cancer. RNA deep-sequencing analysis of individually sorted myeloid lineage and tumor epithelial cells revealed cell-type-specific differentially regulated genes, indicative of activated stroma. We developed a computational model for crosstalk signaling discovery based on ligand-receptor interactions and downstream signaling networks and identified known and novel tumor-stroma paracrine and tumor autocrine crosstalk-signaling pathways in NSCLC. We provide cellular and molecular insights into components of the lung cancer microenvironment that contribute to carcinogenesis. This study has the potential for development of therapeutic strategies that target tumor-stroma interactions and may complement conventional anti-cancer treatments.