A new species of gobiid fish, Tomiyamichthys stuarti, is described from Milne Bay Province, eastern Papua New Guinea, on the basis of three male specimens, 20.4–23.5 mm SL. Diagnostic features include 11 segmented dorsal-fin and anal-fin rays, 15 pectoral-fin rays, 51–56 lateral and 11 transverse scales, no preopercular pores (no M’, N, and O’), no pores above the operculum (no K’ and L’), no prepelvic or prepectoral scales, ctenoid posterior body scales, and color pattern. The markings on the new species consist of 5 large brown blotches on the side of the body with about 9 brown saddles on the upper back, orange spots on the dorsal fins and upper caudal fin, and yellow pelvic and anal fins. Type specimens were collected from a flat mud bottom in 30 m depth.