Alterations in DNA methylation have been proposed as a mechanism for the complex toxicological effects of arsenic. In this study, whole-genome DNA methylation and gene expression changes were evaluated in lungs from female mice exposed for 90 days to 50 ppm arsenate (As) in drinking water. DNA methylation changes were measured using reduced representation bisulfite deep sequencing. Differential methylation was observed in approximately 700 and 1900 start and transcribed regions, respectively. The start regions showed bias toward decreased methylation. No bias was observed in the transcribed region. A comparison of absolute methylation levels in the control animals with treatment-related changes in methylation showed that baseline methylation levels play a role in determining which genes are methylated. Genes with low absolute methylation levels in the start region showed a trend toward increased As-related methylation and decreased expression. Genes with high levels of methylation in the transcribed region showed a trend toward decreased As-related methylation, but no change in expression. No overall correlation between treatment-related changes in methylation and expression was identified. Among genes showing differential methylation in the start region and differential expression, only 57% showed an inverse correlation. The results suggest that differential methylation following As treatment may only play a permissive role in regulating expression. Despite the low correlation, the subset of 17 genes that showed an inverse relationship between As-related methylation and expression included a substantial number that has been demonstrated to play a functional role in cancer-related processes and other effects consistent with arsenic exposure.