Epigenetic alterations are widespread in cancer and can complement genetic alterations to influence cancer progression and treatment outcome. To determine the potential contribution of DNA methylation alterations to tumor phenotype in non-small cell lung cancer (NSCLC) in both smoker and never-smoker patients, we performed genome-wide profiling of DNA methylation in 17 primary NSCLC tumors and 10 matched normal lung samples using the complementary assays methylation DNA immunoprecipitation (MeDIP-seq) and methylation sensitive restriction enzyme digestion followed by sequencing (MRE-seq). We reported recurrent methylation changes of several gene promoters, many previously implicated in cancer, including FAM83A and SEPT9 (hypomethylation), as well as PCDH7, NKX2-1, and SOX17 (hypermethylation). Although many methylation changes between tumors and their paired normal samples were shared across patients, several were specific to a particular smoking status. For example, never-smokers displayed a greater proportion of hypomethylated differentially methylated regions (hypoDMRs) and a greater number of recurrently hypomethylated promoters, including those of ASPSCR1, TOP2A, DPP9, and USP39, all previously linked to cancer. Changes outside of promoters were also widespread and often recurrent, particularly methylation loss over repetitive elements, highly enriched for ERV1 subfamilies. Recurrent hypoDMRs were enriched for several transcription factor binding motifs, often for genes involved in signaling and cell proliferation. For example, 71% of recurrent promoter hypoDMRs contained a motif for NKX2-1. Finally, the majority of DMRs were located within an active chromatin state in tissues profiled using the Roadmap Epigenome data, suggesting that methylation changes may contribute to altered regulatory programs through the adaptation of cell type-specific expression programs.