Background: One of the major challenges in obesity treatment is to explain the high variability in the individual’s response to specific dietary and physical activity interventions. With this study, we tested the hypothesis that specific DNA methylation changes reflect individual responsiveness to lifestyle intervention and may serve as epigenetic predictors for a successful weight-loss. Methods: We conducted an explorative genome-wide DNA methylation analysis in blood samples from 120 subjects (90% men, mean ± SD age = 49 ± 9 years, body mass-index (BMI) = 30.2 ± 3.3 kg/m2) from the 18-month CENTRAL randomized controlled trial who underwent either Mediterranean/low-carbohydrate or low-fat diet with or without physical activity. Results: Analyses comparing male subjects with the most prominent body weight-loss (responders, mean weight change − 16%) vs. non-responders (+ 2.4%) (N = 10 each) revealed significant variation in DNA methylation of several genes including LRRC27, CRISP2, and SLFN12 (all adj. P < 1 × 10−5). Gene ontology analysis indicated that biological processes such as cell adhesion and molecular functions such as calcium ion binding could have an important role in determining the success of interventional therapies in obesity. Epigenome-wide association for relative weight-loss (%) identified 15 CpGs being negatively correlated with weight change after intervention (all combined P < 1 × 10− 4) including new and also known obesity candidates such as NUDT3 and NCOR2. A baseline DNA methylation score better predicted successful weight-loss [area under the curve (AUC) receiver operating characteristic (ROC) = 0.95–1.0] than predictors such as age and BMI (AUC ROC = 0.56). Conclusions: Body weight-loss following 18-month lifestyle intervention is associated with specific methylation signatures. Moreover, methylation differences in the identified genes could serve as prognostic biomarkers to predict a successful weight-loss therapy and thus contribute to advances in patient-tailored obesity treatment.