Understanding the molecular basis of stress is of long standing interest in biology and fish science. We tackled this question by modifying the epiGBS (epiGenotyping By sequencing) technique to screen for cytosine methylation and explore the genome-wide epigenomic response to a repeated acute stress challenge in the European sea bass (Dicentrarchus labrax). Following a minimally invasive sampling using nucleated red blood cells (RBCs), our modified epiGBS protocol retrieved 501,108,033 sequencing reads after trimming, with a mean mapping efficiency of 73.0% (unique best hits). Sequencing reads mapped across all linkage groups (LGs). A total of 47,983 CpG coordinates with a minimum 30X read depth was retained for differential methylation analysis between pre- and post-stress fish. A family effect was demonstrated, and 57 distinct differentially methylated cytosines (DMCs) distributed on 17 of 24 LGs were found between RBCs of pre- and post-stress individuals and located close to 51 distinct stress-related genes. Thirty-eight of these genes were previously reported as differentially expressed in the brain of zebrafish, most of them involved in stress coping differences. Some DMC-related genes appear as good candidates to study the stress response, especially a set of them associated to the Brain Derived Neurotrophic Factor (BDNF), a protein that favors stress adaptation and fear memory. Limits to our study and future directions are presented, including the use of RBCs as a surrogate to other target tissues, to provide with classical physiological measurements a more complete picture of the stress response in fish.