Background: In fish, minimally invasive blood sampling is widely used to monitor physiological stress with blood plasma biomarkers. As fish blood cells are nucleated, they might be a source a potential new markers derived from 'omics technologies. We modified the epiGBS (epiGenotyping By Sequencing) technique to explore changes in genome-wide cytosine methylation in the red blood cells (RBCs) of challenged European sea bass (Dicentrarchus labrax), a species widely studied in both natural and farmed environments. Results: We retrieved 501,108,033 sequencing reads after trimming, with a mean mapping efficiency of 73.0% (unique best hits). Minor changes in RBC methylome appeared to manifest after the challenge test and a familyeffect was detected. Only fifty-seven differentially methylated cytosines (DMCs) close to 51 distinct genes distributed on 17 of 24 linkage groups (LGs) were detected between RBCs of pre-and post-challenge individuals. Thirty-seven of these genes were previously reported as differentially expressed in the brain of zebrafish, most of them involved in stress coping differences. While further investigation remains necessary, few DMC-related genes associated to the Brain Derived Neurotrophic Factor, a protein that favors stress adaptation and fear memory, appear relevant to integrate a centrally produced stress response in RBCs. Conclusion: Our modified epiGBS protocol was powerful to analyze patterns of cytosine methylation in RBCs of D. labrax and to evaluate the impact of a challenge using minimally invasive blood samples. This study is the first approximation to identify epigenetic biomarkers of exposure to stress in fish.