Five new species belonging to the gobiid fish genus Grallenia of the tropical western Pacific Ocean are described from sand-bottom habitats. G. compta n. sp. (11 specimens, 14.9–17.3 mm SL) from Milne Bay Province, Papua New Guinea and G. rubrilineata n. sp. (81 specimens, 8.8–15.8 mm SL) from Luzon, Philippines share a suite of features that comprises an absence of cephalic sensory-canal pores, a rectangular first dorsal fin without a filamentous extension of the first spine, and the anterior and posterior scales separated by a scaleless gap, with 15–22 longitudinal scales in the posterior series. The two species differ from each other in dorsal- and anal fin-ray counts (8–9 for G. compta n. sp. vs. 9–11, usually 10, for G. rubrilineata n. sp.), scalation patterns, and coloration. A third new species, Grallenia dimorpha n. sp. (34 specimens, 9.8–16.7 mm SL) from Papua New Guinea is similar, except it has a continuous series of longitudinal scales without a gap, and females possess a triangular first dorsal fin featuring a filamentous extension of the first spine. The last two species, Grallenia lauensis n. sp. (two females, 11.1–11.4 mm SL) and G. solomonensis n. sp. (three females, 11.4–12.5 mm SL), are described from Fiji and the Solomon Islands, respectively. They exhibit similar diagnostic features including the presence of cephalic sensory-canal pores, usually 7 segmented dorsal- and anal-fin rays, and most body scales restricted to the caudal peduncle. Grallenia solomonensis n. sp. differs from G. lauensis n. sp. in having several mid-lateral scales immediately behind the pectoral-fin base (vs. none), 16 (vs. 15) pectoral-fin rays, pelvic-fin rays with 2–3 branch points (vs. a single point), and a truncate (vs. slightly emarginate) caudal fin. An additional 33 non-type specimens, 7.0–15.6 mm SL, from Australia (southern Great Barrier Reef and northwestern Coral Sea) are provisionally identified as G. lauensis n. sp. However, at least some Australian specimens differ slightly in possessing branched segmented dorsal-fin rays and pelvic-fin rays with more than one branch point. Although fins are damaged in most specimens, two Australian males exhibit a long, filamentous first dorsal-fin spine.