Abstract Aim The value of frequent Carcino-Embryonic Antigen (CEA) measurements and CEA-triggered imaging for detecting recurrent disease in colorectal cancer (CRC) patients was investigated in search for an evidence-based follow-up protocol. Methods This is a randomized-controlled multicenter prospective study using a stepped-wedge cluster design. From October 2010 to October 2012, surgically treated non-metastasized CRC patients in follow-up were followed in eleven hospitals. Clusters of hospitals sequentially changed their usual follow-up care into an intensified follow-up schedule consisting of CEA measurements every two months, with imaging in case of two CEA rises. The primary outcome measures were the proportion of recurrences that could be treated with curative intent, recurrences with definitive curative treatment outcome, and the time to detection of recurrent disease. Results 3223 patients were included; 243 recurrences were detected (7.5%). A higher proportion of recurrences was detected in the intervention protocol compared to the control protocol (OR = 1.80; 95%-CI: 1.33-2.50; p = 0.0004). The proportion of recurrences that could be treated with curative intent was higher in the intervention protocol (OR = 2.84; 95%-CI: 1.38-5.86; p = 0.0048) and the proportion of recurrences with definitive curative treatment outcome was also higher (OR = 3.12, 95%-CI: 1.25-6.02, p-value: 0.0145). The time to detection of recurrent disease was significantly shorter in the intensified follow-up protocol (HR = 1.45; 95%-CI: 1.08-1.95; p = 0.013). Conclusion The CEAwatch protocol detects recurrent disease after colorectal cancer earlier, in a phase that a significantly higher proportion of recurrences can be treated with curative intent.