Unlike the better-studied aberrant epigenome in the tumor, the clinicopathologic impact of DNA methylation in the tumor microenvironment (TME), especially the contribution from cancer-associated fibroblast (CAF), remains elusive. CAFs exhibit profound patient-to-patient tumorigenic heterogeneity. We ask whether such heterogeneity may be exploited to quantify the level of TME malignancy or not. We developed a robust and efficient methylome/transcriptome co-analysis system for CAFs and paired normal fibroblasts (NFs) from non-small-cell lung cancer patients. We found 14,781 CpG sites of CAF/NF differential methylation, of which 3,707 sites showed higher methylation changes in ever-smokers than in non-smokers. Concomitant CAF/NF differential gene expression analysis pinpointed to a subset of 54 smoking-associated CpG sites with strong methylation-regulated gene expression. A methylation index that summarizes the beta-values of these CpGs was built for NF/CAF discrimination (MIND) with high sensitivity and specificity. The potential of MIND in detecting pre-malignancy across individual patients was shown. MIND succeeded in predicting tumor recurrence in multiple lung cancer cohorts without reliance on patient survival data, suggesting that the malignancy level of TME may be effectively graded by this index. Precision TME grading may provide additional pathological information to guide cancer prognosis and open up more options in personalized medicine.