Background: Epigenetic mechanisms provide an interface between environmental factors and the genome and are known to play a role in complex diseases such as obesity. These mechanisms, including DNA methylation, influence the regulation of development, differentiation and the establishment of cellular identity. Here we employ two approaches to identify differential methylation between two white adipose tissue depots in obese individuals before and after gastric bypass and significant weight loss. We analyse genome-wide DNA methylation data using (a) traditional paired t tests to identify significantly differentially methylated loci (Bonferroni-adjusted P≤1×10−7) and (b) novel combinatorial algorithms to identify loci that differentiate between tissue types. Results: Significant differential methylation was observed for 3239 and 7722 CpG sites, including 784 and 1129 extended regions, between adipose tissue types before and after significant weight loss, respectively. The vast majority of these extended differentially methylated regions (702) were consistent across both time points and enriched for genes with a role in transcriptional regulation and/or development (e.g. homeobox genes). Other differentially methylated loci were only observed at one time point and thus potentially highlight genes important to adipose tissue dysfunction observed in obesity. Strong correlations (r>0.75, P≤0.001) were observed between changes in DNA methylation (subcutaneous adipose vs omentum) and changes in clinical trait, in particular for CpG sites within PITX2 and fasting glucose and four CpG sites within ISL2 and HDL. A single CpG site (cg00838040, ATP2C2) gave strong tissue separation, with validation in independent subcutaneous (n=681) and omental (n=33) adipose samples. Conclusions: This is the first study to report a genome-wide DNA methylome comparison of subcutaneous abdominal and omental adipose before and after weight loss. The combinatorial approach we utilised is a powerful tool for the identification of methylation loci that strongly differentiate between these tissues. This study provides a solid basis for future research focused on the development of adipose tissue and its potential dysfunction in obesity, as well as the role DNA methylation plays in these processes.