Background: Aberrant DNA methylation is involved in gastric carcinogenesis and may serve as a useful biomarker in the diagnosis and detection of gastric cancer (GC) recurrence. Results: A total of 157 patients who received surgery for GC were enrolled in the present study. A genome-wide methylation analysis was performed in tumor and adjacent normal tissues for the discovery set of 16 GC patients; the top three hypermethylated CpG sites of DNA promoters were selected for validation in tissue and plasma samples for the validation set of 141 GC patients. The frequencies of the top three hypermethylated genes in available patient tissues (n = 141) and plasma samples (n = 106) were 41.8% and 38.7%, respectively, for ADAM19; 40.4% and 42.5%, respectively, for FLI1; and 56.7% and 50.9%, respectively, for MSC. In both tissue and plasma samples, FLI1 hypermethylation was associated with more advanced GC and liver and distant lymphatic metastasis, and ADAM19 hypermethylation was associated with more stage IV GC. In plasma samples, MSC hypermethylation was more common in non-superficial type GC than samples without MSC hypermethylation. In both tissue and plasma samples, patients with methylation of all the three genes had significantly more liver metastases, distant lymphatic metastases, and paraaortic lymph node metastases than patients with two or fewer hypermethylated genes. The survival analysis showed that only for stage III GC, patients with hypermethylation of two or three genes had a worse 5-year disease-free survival rate than those with hypermethylation of one or none of the three genes. Subgroup analysis showed that FLI1 hypermethylation in both tissue and plasma samples was associated with liver metastasis in MSI-/EBV- GC, and MSC hypermethylation in tissue samples was correlated with liver metastasis in MSI+ or EBV+ GC. Patients with FLI1 hypermethylation in plasma samples had a significantly worse 5-year disease-free survival rate than those without FLI1 hypermethylation in MSI-/EBV- GC. FLI1 hypermethylation was an independent prognostic factor affecting the overall survival and disease-free survival in both tissue and plasma samples. Conclusions: DNA methylation is a useful biomarker for predicting tumor recurrence patterns and GC patient survival.