A new gobiid fish, Vanderhorstia papilio, is described based on a single specimen (40.9mm SL) captured from a sandy-mud bottom at a depth of 45m in a protected bay of Iriomote-jima Island, Ryukyu Islands, Japan. It is distinguished from congeners in having the following combination of characters: 11 segmented dorsal-fin rays; 11 segmented anal-fin rays; 27 longitudinal scales; 11 predorsal scales; third spine of first dorsal fin elongate, filamentous, and longer than preceding spine; fifth and ninth branched caudal-fin rays elongate, filamentous, and forming bifurcated caudal fin; fifth and ninth branched caudal-fin rays with a single branch in each; cephalic sensory-papillae row a comprises three widely-spaced papillae; when live or fresh, numerous small yellow spots scattered on head, body, and dorsal fins; dusky yellowish-brown vertical bar below eye; four dark gray-brown saddles on body, in addition to a similarly colored large blotch at midlateral caudal-fin base. The limits and diagnosis of the genus Vanderhorstia are discussed.