Population genetic studies of species inhabiting the deepest parts of the oceans are still scarce and only until recently we started to understand how oceanographic processes and topography affect dispersal and gene flow patterns. The aim of this study was to investigate the spatial population genetic structure of the bathyal bony fish Coryphaenoides mediterraneus, with a focus on the Atlantic-Mediterranean transition. We used nine nuclear microsatellites and the mitochondrial cytochrome c oxidase I gene from 6 different sampling areas. No population genetic structure was found within Mediterranean with both marker types (mean ΦST = 0.0960, FST = -0.0003, for both P > 0.05). However, within the Atlantic a contrasting pattern of genetic structure was found for the mtDNA and nuclear markers (mean ΦST = 0.2479, P < 0.001; FST = -0.0001, P > 0.05). When comparing samples from Atlantic and Mediterranean they exhibited high and significant levels of genetic divergence (mean ΦST = 0.7171, FST = 0.0245, for both P < 0.001) regardless the genetic marker used. Furthermore, no shared haplotypes were found between Atlantic and Mediterranean populations. These results suggest very limited genetic exchange between Atlantic and Mediterranean populations of C. mediterraneus, likely due to the shallow bathymetry of the Strait of Gibraltar acting as a barrier to gene flow. This physical barrier not only prevents the direct interactions between the deep-living adults, but also must prevent interchange of pelagic early life stages between the two basins. According to Bayesian simulations it is likely that Atlantic and Mediterranean populations of C. mediterraneus were separated during the late Pleistocene, which is congruent with results for other deep-sea fish from the same region.