Two new species of the gobiid genus Hetereleotris, H. aurantiaca sp. nov. and H. semisquamata sp. nov., are described from the Red Sea, the former from Saudi Arabia at Jeddah from the cave at depth of 14–16 m, and the latter from the southern Egypt from reef flat. Hetereleotris aurantiaca sp. nov. is distinguished from its congeners by having dorsal-fin rays VI + I,10; anal-fin rays I,9; pectoral-fin rays 14, all rays branched; pelvic-fin rays I,5, the fin separated and without frenum, 5th ray unbranched; anterior nostril with a long tube without process from the rim, posterior nostril a pore with erected rim; no tentacle above eye; posterior angle of jaws extending posteriorly to below posterior edge of pupil; no opercular spine; no mental frenum; pelvic fins longer than pectoral fins; squamation reduced to a few scales on caudal peduncle at caudal-fin base; no head canals; by presence, size and pattern of suborbital rows of sensory papillae; and orange head and yellowish orange body with five faint brown bars. Hetereleotris semisquamata sp. nov. is distinctive among its congeners by unique scale pattern (scales cycloid, the squamation reduced, tapering from caudal-fin base along lateral midline towards pectoral fin where nearly reaching its base) and by coloration (head and body whitish, with brown line from eye to end of upper lip, dark brown band across interorbital area and continuing obliquely from eye to corner of opercle, broad dark brown band below first dorsal fin continuing into fin, and moderately broad dark brown bar on caudal-fin base). Furthermore, it is characterized in having dorsal-fin rays VI + I,11, anal-fin rays I,10, pectoral-fin rays 16, and absence of head canals. In addition to descriptions of two species, a key to all species of Hetereleotris is provided. Hetereleotris psammophila is reported outside the Gulf of Aqaba for the first time.