Background: Garra barreimiae is a cyprinid fish from the southeastern Arabian Peninsula, which inhabits regularly desiccating wadis and survives in isolated ponds or underground. In 1984 a cave-dwelling population was found in the Al Hoota cave system and previous genetic analyses revealed some differentiation with limited gene flow between the surface populations and the cave population. Since no suitable markers are available for evaluation of gene flow between the cave population and the adjacent surface populations, we focused on designing and establishing novel microsatellite markers from next generation sequencing data. Findings: 19 microsatellite markers containing di- and tetranucleotide simple sequence repeats were developed from 454 sequences. Forty-four individuals from two surface populations (Wadi Al Falahi and Misfat Al Abriyeen) of G. barreimiae (sampling permission number 13/2012, export permission number 29/2012) were used for analyses and characterization of the loci. On average, the number of alleles per locus is 7.6 (range: 2–20). Two markers displayed indication of linkage disequilibrium in both populations (DL6X, 9XNC). Significant deviation from Hardy-Weinberg equilibrium was observed at four loci in the Misfat Al Abriyeen population (2PUM, 88CM, 1EHE, 3Z7M) and at two loci in the Wadi Al Falahi population (QLIM, 3 N43). Three of the microsatellite loci were significant for null alleles in one of the two populations (Misfat Al Abriyeen: CJHG; Wadi Al Falahi: PH8A, 3ROZ). Expected and observed heterozygosities ranged from 0 to 95.0% respectively from 0 to 95.8% (Wadi Al Falahi) and from 0 to 89.1% respectively from 0 to 95.0% (Misfat Al Abriyeen). Fourteen of these markers were successfully cross-amplified in G. rufa. Conclusion: This 19 microsatellite loci provide a useful tool to understand the structure and genetic differences of populations. Moreover, these markers will help to evaluate species delimitation in G. barreimiae and potentially even in related species.