The adaptive response of skeletal muscle to exercise training is tightly controlled and therefore requires transcriptional regulation. DNA methylation is an epigenetic mechanism known to modulate gene expression, but its contribution to exercise-induced adaptations in skeletal muscle is not well studied. Here, we describe a genome-wide analysis of DNA methylation in muscle of trained mice (n = 3). Compared with sedentary controls, 2,762 genes exhibited differentially methylated CpGs (P < 0.05, meth diff >5%, coverage >10) in their putative promoter regions. Alignment with gene expression data (n = 6) revealed 200 genes with a negative correlation between methylation and expression changes in response to exercise training. The majority of these genes were related to muscle growth and differentiation, and a minor fraction involved in metabolic regulation. Among the candidates were genes that regulate the expression of myogenic regulatory factors (Plexin A2) as well as genes that participate in muscle hypertrophy (Igfbp4) and motor neuron innervation (Dok7). Interestingly, a transcription factor binding site enrichment study discovered significantly enriched occurrence of CpG methylation in the binding sites of the myogenic regulatory factors MyoD and myogenin. These findings suggest that DNA methylation is involved in the regulation of muscle adaptation to regular exercise training.