We investigate the presence of cryptic species among three highly variable nereidid polychaetes commonly found in Australian coral reefs - Nereis denhamensis Augener, 1913, Perinereis suluana (Horst, 1924) and Pseudonereis anomala Gravier, 1901 - based on morphological and molecular data (mitochondrial cytochrome c oxidase subunit I, COI, and nuclear histone H3). DNA extracted and sequenced from 70 specimens from northern Australia and the Philippines indicated the existence of eight species: three matched the types of existing species; four are newly described (Nereis heronensis, sp. nov., N. lizardensis, sp. nov., Perinereis pictilis, sp. nov. and Pseudonereis anomalopsis, sp. nov.) from NE Australia, and one species is described but not named due to lack of material. Nereis denhamensis, N. heronensis, sp. nov. and N. lizardensis, sp. nov. are distinguished from each other by proboscidial paragnath number and morphology of the metamorphosed female. Perinereis suluana can only be separated from P. pictilis, sp. nov. by colour pattern, while Pseudonereis anomala, P. anomalopsis, sp. nov. and P. sp. differ in colour pattern and the number and arrangement of paragnaths. Nereis (Lycoris) tydemani from Maluku, Indonesia, is newly synonymised with P. anomala. Divergence times estimated using COI indicated that speciation in all three groups occurred in the mid Miocene (20–17 ± 7 mya), which corresponds to a period of restricted east–west dispersal as Australia collided with the Indo-Malay archipelago, followed by range expansion opportunities in NE Australia as a result of flourishing coral reefs responding to warming seas and rising sea levels.