Nemateleotris lavandula, new species, is described on the basis of the holotype from Augulupelu Reef, Palau, and twelve paratypes from across the western and central Pacific Ocean, including Fiji, Guam, Japan, and the Marshall Islands. The new species was previously confused with Nemateleotris helfrichi, but molecular analysis of mitochondrial COI reveals a difference of 1% in sequence data between both species, in addition to differences in morphometric measurements, live, and preserved colouration details. Both species are allopatric and do not overlap in distribution. The new species is readily separated from all congeners based on the following combination of characters: body lavender to lilac in life; maxilla unmarked, bright yellow in life; caudal fin truncate to weakly emarginate, unmarked, pale yellowish green in life; and snout, lower jaw, preopercle, and postorbital region bright yellow in life. We comment on the relationships among species of Nemateleotris, the taxonomic status of N. exquisita, and the doubtful identity of Zagadkogobius ourlazon. A revised key to species of Nemateleotris is provided.