Genomic data allow an in-depth and renewed study of local adaptation. The red coral (Corallium rubrum, Cnidaria) is a highly genetically structured species and a promising model for the study of adaptive processes along an environmental gradient. Here, we used RAD-Sequencing in order to study the vertical genetic structure of this species and to search for signals of local adaptation to depth and thermal regime in the red coral. Previous studies have shown different thermotolerance levels according to depth in this species which could correspond to genetic or environmental differences. We designed a sampling scheme with six pairs of ‘shallow vs deep’ populations distributed in three geographical regions as replicates. Our results showed significant differentiation among locations and among sites separated by around 20 m depth. The tests of association between genetics and environment allowed the identification of candidate loci under selection but with a potentially high rate of false positive. We discuss the methodological obstacles and biases encountered for the detection of selected loci in such a strongly genetically structured species. On this basis, we also discuss the significance of the candidate loci for local adaptation detected in each geographical region and the evolution of red coral populations along environmental gradients.