Priolepis goldshmidtae n. sp. was collected at a depth of 400 m in the northern Gulf of Aqaba, Red Sea. The new species is characterized by LS 26-27; PreD 15; D: VI, I 10-11; A: I 9; P 20-21. Gill opening to below rear margin of eye; 17-18 gillrakers, long and slender, lacking spinucles. Body red (pale-brown in preserved fish) with 4-5 narrow, backward-directed light bars, a wide vertical bar in from of first dorsal fin and 3 forward-directed bars on head. Priolepis species are reef associated gobies and the present finding of this species at a depth of 400 m where no coral reefs exist, is an indication for the presence of hard substrate on the soft bottom of the deep sea.