Background: There is a general lack of information on the dispersal and genetic structuring for populations of small-sized deep-water taxa, including free-living nematodes which inhabit and dominate the seafloor sediments. This is also true for unique and scattered deep-sea habitats such as cold seeps. Given the limited dispersal capacity of marine nematodes, genetic differentiation between such geographically isolated habitat patches is expected to be high. Against this background, we examined genetic variation in both mitochondrial (COI) and nuclear (18S and 28S ribosomal) DNA markers of 333 individuals of the genus Sabatieria, abundantly present in reduced cold-seep sediments. Samples originated from four Eastern Mediterranean cold seeps, separated by hundreds of kilometers, and one seep in the Southeast Atlantic. Results: Individuals from the Mediterranean and Atlantic were divided into two separate but closely-related species clades. Within the Eastern Mediterranean, all specimens belonged to a single species, but with a strong population genetic structure (Phi(ST) = 0.149). The haplotype network of COI contained 19 haplotypes with the most abundant haplotype (52% of the specimens) shared between all four seeps. The number of private haplotypes was high (15), but the number of mutations between haplotypes was low (1-8). These results indicate intermediary gene flow among the Mediterranean Sabatieria populations with no evidence of long-term barriers to gene flow. Conclusions: The presence of shared haplotypes and multiple admixture events indicate that Sabatieria populations from disjunct cold seeps are not completely isolated, with gene flow most likely facilitated through water current transportation of individuals and/or eggs. Genetic structure and molecular diversity indices are comparable to those of epiphytic shallow-water marine nematodes, while no evidence of sympatric cryptic species was found for the cold-seep Sabatieria.