Epigenetic modification of cytosine methylation states can be elicited by environmental stresses and may be a key process affecting phenotypic plasticity and adaptation. Parasites are potent stressors with profound physiological and ecological effects on their host, but there is little understanding in how parasites may influence host methylation states. Here, we estimate epigenetic diversity and differentiation among 21 populations of red grouse (Lagopus lagopus scotica) in north-east Scotland, and test for association of gastro-intestinal parasite load (caecal nematode Trichostrongylus tenuis) with hepatic genome-wide and locus-specific methylation states. Following methylation-sensitive AFLP (MSAP), 129 bands, representing 73 methylation-susceptible and 56 non-methylated epiloci, were scored across 234 individuals. The populations differed significantly in genome-wide methylation levels and were also significantly epigenetically (FST = 0.0227; p < 0.001) and genetically (FST = 0.0058; p < 0.001) differentiated. Parasite load was not associated with either genome-wide methylation levels or epigenetic differentiation. Instead, we found eight disproportionately differentiated epilocus-specific methylation states (FST -outliers) using bayescan software and significant positive and negative association of 35 methylation states with parasite load from bespoke generalised estimating equations (GEE), simple logistic regression (sam) and Bayesian environmental analysis (bayenv). Following Sanger sequencing, genome mapping and geneontology (go) annotation, some of these epiloci were linked to genes involved in regulation of cell cycle, signalling, metabolism, immune system and notably rRNA methylation, histone acetylation and small RNAs. These findings demonstrate an epigenetic signature of parasite load in populations of a wild bird and suggest intriguing physiological effects of parasite-associated cytosine methylation.