Background: After radical surgery, patients with esophageal cancer should undergo long-term surveillance of disease relapse. However, the optimal follow-up strategy remains to be explored. Method: A total of 4688 patients were recruited. Recursive partition analysis was applied to develop recurrence risk stratification for patients. The follow-up strategies of each stratification were developed based on monthly recurrence probability and validated by bootstrap validation and an external dataset. Markov decision-analytic model was constructed to evaluate the cost-effectiveness of the follow-up strategies. Results: Patients were stratified into four groups according to four pathological features. We applied random survival forest to calculate the monthly recurrence probability of each group. Based on the temporal distribution of recurrences, we further established surveillance strategies for four groups. The strategies were validated as optimal protocols by bootstrap resampling and another dataset. Markov decision-analytic analysis indicated that our recommended strategies outperformed the mainstream protocols from guidelines and were most cost-effective. Using less than 12 visits across the first 5 years on average, our follow-up strategies were more efficient than the NCCN recommended strategies (14 visits average). Our results also supported the computerized tomography from the neck to the upper abdomen as routine examination and PETCT of distant metastasis for some groups with high risks. Conclusion: Our study provided data-driven evidence of personalized and economic follow-up strategies for EC patients and shed light on follow-up optimization for other cancer types.