A new species of the genus Hetereleotris is described from the Gulf of Aqaba, Red Sea, on the basis of two specimens. Hetereleotris psammophila sp. nov. is unique among the species of the genus Hetereleotris, except for H. diademata, in lacking scales and head pores. The new species differs from the morphologically similar H. diademata in having fewer rays in the second dorsal and anal fins, and in coloration. The habitat preference of the new species for open sand area close to coral reefs in 8-21 m and its nocturnal habits are unusual for species of the genus Hetereleotris.