A new species of goby, Lubricogobius tunicatus, is described from Milne Bay Province, eastern Papua New Guinea, on the basis of 10 adult specimens, 9.1–11.5 mm SL. Diagnostic features include 9 (rarely 10) segmented dorsal-fin rays, 6–7 segmented anal-fin rays, the presence of both anterior and posterior nostrils, the greatest body depth 3.1–3.7 in SL, overall coloration typically pale yellow to whitish (rarely brown), and an exceptionally small maximum size of about 11.5 mm SL. Lubricogobius tunicatus is most similar in appearance to L. nanus Allen, 2015, another diminutive species from Papua New Guinea that differs in having 10–11 dorsal-fin rays and 8–9 anal-fin rays. The new species is apparently invariably associated with a species of tunicate (Polycarpa sp.) on silty-sand bottoms in depths of about 20–28 m. In addition, L. ornatus Fourmanoir, 1966, originally described from Vietnam and also recorded from the Ryukyu Islands in Japan, northern Australia, and New Caledonia, is reported for the first time from the East Indies, based on two specimens collected at Lembeh Strait, North Sulawesi, Indonesia.