A new cryptobenthic gobiid species Hetereleotris nasoramosa sp. nov. is described based on the holotype and five paratypes collected from the north-eastern part of Socotra Island, Arabian Sea, from moderately large pieces of coral rocks with holes at depths of 811 m. Molecular phylogenetic analysis placed the new species within the genus Hetereleotris. Hetereleotris nasoramosa sp. nov., differs from all species of Hetereleotris in having developed tentacles extending from each anterior and posterior nostril and five transverse suborbital papillae rows (instead four or six in other species). The new species superficially resembles the recently described Red Sea endemic species Cerogobius petrophilus by having forward-set, elevated eyes, a short snout, a moderately large mouth, a relatively deep and short caudal peduncle, and developed tentacles on the head, but differs from it by the same characters of developed tentacles extending from each anterior and posterior nostril and five transverse suborbital papillae rows as from other Hetereleotris species. Both species also share a specific habitat preference for tight holes in rock covered by micro-algae. A full description of the species is provided as well as a revised key to the species of Hetereleotris.