Tomiyamichthys dorsostigma is described as a new species of goby from two specimens collected in the Gulf of Aqaba. It was first identified as T. fourmanoiri Smith, 1959, known from one specimen from Madagascar. It differs in having a longer head, the penultimate dorsal soft ray longest, longer paired fins, and in colour pattern. T. dorsostigma is more similar to another closely related species, T. smithi (Chen & Fang, 2003), differing in colour pattern and the high number of 120-125 scales in longitudinal series. The sand-dwelling, shallow-water gobiid fishes Macrodontogobius wilburi, Papillogobius melanobranchus, and Vanderhorstia ornatissima are reported as first records for the Red Sea. Diagnoses, colour photographs, notes on ecology, and comparisons with similar species are provided. Psilogobius randalli, previously known from two specimens from the Gulf of Aqaba, was recently photographed at Marsa Alam, southern Egypt.