Non-small cell lung cancer (NSCLC) is one of the most commonly diagnosed and deadliest cancers worldwide, with roughly half of all patients initially presenting with both primary and metastatic disease. While the major events in the metastatic cascade have been identified, a mechanistic understanding of how NSCLC routinely and successfully colonizes the brain is largely unknown. Recent studies have begun demonstrating the role of epigenetic misregulation during tumorigenesis and metastasis, including widespread changes in DNA methylation and histone modifications. To better understand the role of altered DNA methylation in NSCLC metastasis to the brain, we measured DNA methylation during disease progression for 12 patients, globally profiling the methylation status of normal lung, primary lung tumor, and brain metastasis samples. The variation in methylation was similar during metastatic spread and primary tumorigenesis but less coordinated across genomic features during metastasis. The greatest recurrent changes during metastatic progression were methylation gains in DNA methylation valleys (DMV) harboring the constitutive heterochromatin mark H3K9me3 as well as bivalent marks H3K27me3 and H3K4me1. In a lymph node-derived cancer cell line, EZH2 binding within DMVs was lost, accompanied by an increase in DNA methylation, exemplifying epigenetic switching. The vast majority of the differentially methylated region-associated DMVs harbored developmental genes, suggesting that altered epigenetic regulation of developmentally important genes may confer a selective advantage during metastatic progression. The characterization of epigenetic changes during NSCLC brain metastasis identified recurrent methylation patterns that may be prognostic biomarkers and contributors to disease progression.