A new species of gobiid fish, Tomiyamichthys elliotensis, is described from Lady Elliot Island at the southern end of Australia’s Great Barrier Reef, on the basis of 6 specimens, 32.6–52.7 mm SL. Diagnostic features include a sail-like first dorsal fin without filamentous elements; 10 segmented dorsal and anal-fin rays; 17 or 18 pectoral-fin rays; scales all cycloid, 78–84 lateral and 18–24 transverse scale rows, no prepectoral scales; and a cephalic sensory-canal pore system containing pores B’, C, D, E, F, G, H’, M’, N and O’. The fish is overall whitish with a midlateral row of 4 large, ovate, brown spots; diagonal yellow-orange bands on the first dorsal fin; a brown stripe along the mid-second-dorsal fin; several yellow-orange stripes along the anal fin; and bluish pelvic fins with yellow fin rays. Among the 6 species of Tomiyamichthys that have mtDNA COI sequences, interspecific divergences range from 14.4% to 21.5% and the new species is 18.3% different in COI sequence from its putative nearest relative Tomiyamichthys oni. The habitat of the new species consists of relatively flat, sandy bottoms exposed to periodic strong tidal currents in 15–24 m depths.