Spirobranchus tetraceros (Schmarda, 1861) originally briefly described from New South Wales, Australia was later reported as a widely distributed species of Indo-Pacific origin. The species was assumed to be a highly successful invasive Lessepsian migrant to the Mediterranean via the Suez Canal. However, recently, such wide distributions have been questioned and S. tetraceros was treated as a complex of morphologically similar species. Moreover, genetic evidence proved that the species that invaded the Mediterranean originated neither in warm temperate Australia nor in the Red Sea. This study examines the taxonomic status of Spirobranchus tetraceros populations along the east coast of Australia. Given the absence of the holotype, we re-described Spirobranchus tetraceros from New South Wales, designated the neotype supported by DNA sequence data, and fixed Port Botany as the type locality. The phylogenetic analysis revealed the existence of a sympatric cryptic species with a mean genetic distance of 36% (described here as S. schmardai sp. nov.) and proved that the tropical coral-associated specimens from Queensland belong to at least two distinct species. We also suggest resurrecting the name S. multicornis Grube, 1862 for the Red Sea population of the Spirobranchus tetraceros complex. This study calls for a worldwide revision of the complex.