Aberrant DNA methylation plays a crucial role in cancer development; however, prospective evidence of an interaction between molecular biomarkers and cancer staging for predicting the prognosis of colorectal cancer (CRC) is still limited. We examined DNA methylation in tumors and adjacent normal tissues from patients who underwent CRC surgical resection, and evaluated the interaction between cancer staging (advanced vs local) and DNA methylation to predict the prognosis of CRC. We recruited 132 patients with CRC from Tri-Service General Hospital in Taiwan and used the candidate gene approach to select 3 tumor suppressor genes involved in carcinogenesis pathways. ORs and 95% CIs were computed using logistic regression analyses while adjusting for potential covariates. Advanced cancer stage was correlated with cancer recurrence (OR 7.22, 95% CI 2.82 to 18.45; p<0.001). In addition, after stratification by promoter methylation in 3 combined genes in the matched normal tissues, we observed a joint effect after adjusting for sex, age at surgery, and adjuvant chemotherapy, yielding a significant OR of 20.35 (95% CI 4.16 to 99.57; p<0.001). DNA methylation status would significantly increase the recurrence risk of CRC with a significant impact on joint effect between DNA methylation and clinical stage, particularly in matched normal tissues. This was attributed to molecular changes that could not be examined on the basis of clinical pathology. Our interaction results may serve as a reference marker for evaluating the risk of recurrence in future studies.