A new species of gobiid fish, Vanderhorstia vandersteene, is described from the East Cape region of Milne Bay Province, Papua New Guinea on the basis of five specimens 17.5–32.2 mm SL. Diagnostic features include dorsal-fin elements VI-I,10–12; the fourth dorsal-fin spine filamentous, reaching the base of about the fifth to seventh segmented dorsal-fin ray when adpressed; anal-fin rays I,11; pectoral-fin rays 16–18; lateral scales 35–37; transverse scales 10; body scales mostly ctenoid, except cycloid scales anterior to the level of about the second-dorsal-fin origin, as well as on the pectoral-fin base, prepelvic region, and the lower side between the pectoral-fins and pelvic fins; scales absent on the head, including medially and anteriorly on the predorsal region; the caudal fin lanceolate with an elongate, median filament; color in life light neon blue with a wavy yellow-orange stripe from the upper operculum to the upper caudal-fin base, prominent yellow-orange bars, bands, and spots on the head and upper sides, a pair of yellow stripes on the second dorsal fin, and yellow streaks and bands on the caudal fin. We include a key to the Vanderhorstia species with low lateral-scale counts (less than 45).