We present the first large-scale methylome-wide association studies (MWAS) for major depressive disorder (MDD) to identify sites of potential importance for MDD etiology. Using a sequencing-based approach that provides near-complete coverage of all 28 million common CpGs in the human genome, we assay methylation in MDD cases and controls from both blood (N = 1132) and postmortem brain tissues (N = 61 samples from Brodmann Area 10, BA10). The MWAS for blood identified several loci with P ranging from 1.91 × 10−8 to 4.39 × 10−8 and a resampling approach showed that the cumulative association was significant (P = 4.03 × 10−10) with the signal coming from the top 25,000 MWAS markers. Furthermore, a permutation-based analysis showed significant overlap (P = 5.4 × 10−3) between the MWAS findings in blood and brain (BA10). This overlap was significantly enriched for a number of features including being in eQTLs in blood and the frontal cortex, CpG islands and shores, and exons. The overlapping sites were also enriched for active chromatin states in brain including genic enhancers and active transcription start sites. Furthermore, three loci located in GABBR2, RUFY3, and in an intergenic region on chromosome 2 replicated with the same direction of effect in the second brain tissue (BA25, N = 60) from the same individuals and in two independent brain collections (BA10, N = 81 and 64). GABBR2 inhibits neuronal activity through G protein-coupled second-messenger systems and RUFY3 is implicated in the establishment of neuronal polarity and axon elongation. In conclusion, we identified and replicated methylated loci associated with MDD that are involved in biological functions of likely importance to MDD etiology.