The objectives of this study were to describe DNA methylation patterns in leukocytes from dairy cows with variable milk yield, determine associations with gene expression from an independent population, and to identify regions with differential methylation. DNA was extracted from blood samples of 8 lactating Holstein dairy cows with 305 d milk yields ranging from 10,948 kg to 23,105 kg. Following methylated DNA immunoprecipitation, approximately 100 million pair-ended reads per cow were sequenced and aligned to the bovine genome. There were differences among chromosomes (P < 0.05) with the lowest methylation levels observed for the X chromosome and chromosome 6, whereas chromosome 19 had the highest methylation levels. Methylation patterns were described for 13,677 protein coding genes and associations with expression from a separate population determined for 9,750 genes. Gene rich regions had more unique reads mapped than gene poor regions (P < 0.05), but repetitive elements were not considered. Methylation levels were generally low upstream of genes with the nadir occurring 95 base pairs before the transcription start site. Methylation was lower over the first exon than later exons and, for introns, highest near intron-exon junctions. Gene expression became increasing negative as methylation increased until 35 base pairs upstream of the transcription start site, and for higher methylation across the first exon. Regions of differential methylation were evident, including in an immune related gene family on chromosome 19 (SECTM1). Approximately 27% of the genome was associated with 100 kb or larger regions of suppressed methylation, or partially methylated domains (PMD). Functional annotation identified olfactory transduction related genes as enriched in PMD. This study demonstrated that features of the cattle leukocyte methylome were similar to features of other species, including an inverse relationship between promoter methylation levels and gene expression, and the presence of PMD; potential areas of differential methylation were also present that might be able to be exploited for cattle improvement.