Accumulating evidence has suggested the requirement for further stratification of patients in the same tumor stage according to molecular factors. We evaluate the combination of cancer stage and DNA methylation status as an indicator of the risk of recurrence and mortality among patients with colorectal cancer (CRC). A cohort study of 215 patients with CRC (mean age 64.32 years; 50.5% of men) from Tri-Service General Hospital in Taiwan examined the association between cancer stage and risk of CRC recurrence and mortality. A Cox proportional hazard model was used to analyze patient methylation status and clinical information at study entry, and their associations with CRC recurrence and mortality during follow-up. The advanced stage patients with p16, hMLH1, and MGMT methylation were associated with higher risk of CRC recurrence compared with the local stage patients with unmethylation status in tumor tissues, with adjusted hazard ratios (HRs) (95% confidence interval [CI]) of 9.64 (2.92–31.81), 8.29 (3.40–20.22), and 11.83 (3.49–40.12), respectively. When analyzing normal tissues, we observed similar risk of CRC recurrence with adjusted HRs (95% CI) of 10.85 (4.06–28.96), 9.04 (3.79–21.54), and 12.61 (4.90–32.44), respectively. For combined analyses, the risk of recurrence in the patients in advanced stage with DNA methylation in both normal and tumor tissues, compared with local stage with unmethylation, was increased with adjusted HR (95% CI) of 9.37 (3.36–26.09). In the advanced stage patients, methylation status and tissue subtype were associated with increased risk of 5-year cumulative CRC recurrence (p < 0.001). This study demonstrates that clustering DNA methylation status according to cancer stage and tissue subtype is critical for the assessment of risk of recurrence in CRC patients and also indicated an underlying mechanism.