Aberrant DNA methylation in the blood of patients with major depressive disorder (MDD) has been reported in several previous studies. However, no comprehensive studies using medication-free subjects with MDD have been conducted. Furthermore, the majority of these previous studies has been limited to the analysis of the CpG sites in CpG islands (CGIs) in the gene promoter regions. The main aim of the present study is to identify DNA methylation markers that distinguish patients with MDD from non-psychiatric controls. Genome-wide DNA methylation profiling of peripheral leukocytes was conducted in two set of samples, a discovery set (20 medication-free patients with MDD and 19 controls) and a replication set (12 medication-free patients with MDD and 12 controls), using Infinium HumanMethylation450 BeadChips. Significant diagnostic differences in DNA methylation were observed at 363 CpG sites in the discovery set. All of these loci demonstrated lower DNA methylation in patients with MDD than in the controls, and most of them (85.7%) were located in the CGIs in the gene promoter regions. We were able to distinguish patients with MDD from the control subjects with high accuracy in the discriminant analysis using the top DNA methylation markers. We also validated these selected DNA methylation markers in the replication set. Our results indicate that multiplex DNA methylation markers may be useful for distinguishing patients with MDD from non-psychiatric controls.