Background: Major depressive disorder (MDD) exhibits numerous clinical and molecular features that are consistent with putative epigenetic misregulation. Despite growing interest in epigenetic studies of psychiatric diseases, the methodologies guiding such studies have not been well defined. Methods: We performed DNA modification analysis in white blood cells from monozygotic twins discordant for MDD, in brain prefrontal cortex, and germline (sperm) samples from affected individuals and control subjects (total N = 304) using 8.1K CpG island microarrays and fine mapping. In addition to the traditional locus-by-locus comparisons, we explored the potential of new analytical approaches in epigenomic studies. Results: In the microarray experiment, we detected a number of nominally significant DNA modification differences in MDD and validated selected targets using bisulfite pyrosequencing. Some MDD epigenetic changes, however, overlapped across brain, blood, and sperm more often than expected by chance. We also demonstrated that stratification for disease severity and age may increase the statistical power of epimutation detection. Finally, a series of new analytical approaches, such as DNA modification networks and machine-learning algorithms using binary and quantitative depression phenotypes, provided additional insights on the epigenetic contributions to MDD. Conclusions: Mapping epigenetic differences in MDD (and other psychiatric diseases) is a complex task. However, combining traditional and innovative analytical strategies may lead to identification of disease-specific etiopathogenic epimutations.