A new species of gobiid fish, Vanderhorstia dawnarnallae, is described from West Papua Province, Indonesia, on the basis of two male specimens, 39.1 and 39.2 mm SL. Diagnostic features include 13 dorsal-fin and anal-fin segmented rays, third dorsal-fin spine long and filamentous, 47–49 lateral scales, body scales mostly cycloid, posteriormost scales of caudal peduncle finely ctenoid, and scales absent on head and nape region. Color in life is pale greyish to yellowish white with 5 mid-lateral clusters of blue-margined yellow spots with one or two vertical rows of 3–5 blue-margined yellow spots between clusters. The new species is most similar to Vanderhorstia phaeosticta from the western Pacific Ocean, but differs most notably in lacking pronounced sexual dichromatism.