A new species of gobiid fish, Sueviota tubicola, is described from Milne Bay Province, Papua New Guinea, on the basis of nine specimens, 13.0–17.6 mm SL. The new species is most similar to S. larsonae from the Northern Territory of Australia and adjacent Arafura Sea, with both species sharing a suite of features that include an identical pattern of cephalic sensory pores, usually 9 segmented dorsal-fin rays and 8 segmented anal-fin rays, black-tipped anterior nostril tubes, the presence of a full pelvic frenum, and a filamentous first dorsal-fin spine. However, the new species differs from S. larsonae in having a pair of large dark spots on the pectoral-fin base, 26 longitudinal scales (versus 21–24), 14–15 branched pectoral-fin rays (versus 6–9), and the first two dorsal-fin spines elongated (vs. only the first dorsal-fin spine in S. larsonae). Moreover, S. tubicola inhabits shallower depths (20–35 m) compared to the 40–82 m range of S. larsonae. All type specimens of S. tubicola were associated with an unidentified tubeworm that constructs vertical, stick-like structures projecting about 30 cm above the silty-sand substrate and encrusted with sessile invertebrates.