Evidence is emerging that earthworms can evolve tolerance to trace element enriched soils. However, few studies have sought to establish whether such tolerance is determined through adaptation or plasticity. Here we report results from a combined analysis of mitochondrial (cytochrome oxidase II, COII), nuclear (amplified fragment length polymorphism, AFLP) variation and DNA methylation in populations of the earthworm Lumbricus rubellus from sites across an abandoned arsenic and copper mine. Earthworms from the mine site population demonstrated clear arsenic tolerance in comparison to a naïve strain. COII and AFLP results suggest that L. rubellus from the unexposed and the adapted populations comprises two cryptic lineages (Lineages A and B) each of which was present across all of the sites. AFLP analysis by lineage highlighted variations associated with soil metal/metalloid concentrations (most clearly for Lineage A) suggesting a genetic component to the observed tolerance. The methylation sensitive AFLP (Me-AFLP) identified a high genome methylation content (average 13.5%) in both lineages. For Lineage A, Me-AFLP analysis did not identify a strong association with soil arsenic levels. For Lineage B, however, a clear association of methylation patterns with soil arsenic concentrations was found. This suggests that Lineage B earthworms utilise epigenetic mechanisms to adapt to the presence of contamination. These fundamentally different genetic adjustments in the two clades indicate that the two lineages employ distinct adaptive strategies (genetic or epigenetic) in response to arsenic exposure. Mechanisms driving this variation may be founded within the colonisation histories of the lineages.