The new species of gobiid fish, Grallenia larsonae, n. sp. is described based on 104 specimens, 8.1–18.0 mm SL, from northern Australia (Northern Territory and Western Australia). It appears to be closely related to Grallenia arenicola from southern Japan. Both species share a suite of diagnostic features that include the presence of cephalic sensory canals and associated pores, and usually 7 segmented dorsal-fin and anal-fin rays. However, they differ markedly with regard to the pattern of scales covering the body. The new species has relatively few scales anterior to the level of the second dorsal fin origin, and those are usually restricted to a single row, compared with numerous scales that continue forward to the pectoral-fin base in G. arenicola. Comparisons are provided with other members of the genus and an updated key to the species of Grallenia is included.