Lepadichthys bilineatus is described as a new species of gobiesocid fish from a single specimen, 23.5 mm in standard length, collected from 1.5 m in a tidepool on the southeastern coast of Oman. It is distinct from other Lepadichthys species in having the following combination of characters: dorsal-fin rays 16; anal-fin rays 13; pectoral-fin rays 23; principal caudal-fin rays 10; gill rakers 10 on second and third arch; head large, its length 3.1 in SL; body depth 8.0 in SL; disc single; disc length 6.6 in SL; disc width 6.5 in SL; color in alcohol uniform tan; color when fresh: body grayish blue, grading to brownish red posteriorly; head dark brown dorsally, abruptly pale yellowish below eye, with two whitish lines extending posteriorly and slightly ventrally from eye. Lepadichthys erythraeus, a species thus far known only from the Red Sea , is redescribed based on additional diagnostic characteristics and color photos.