A new ascothoracidan species, Gorgonolaureus bicornutus sp. nov., has been discovered off south-eastern Taiwan at a depth of 227 m. Five females were found in permanent cysts on the branches of a plexaurid octocoralian alcyonacean (former “gorgonian”), Echinogorgia sp. These specimens are assigned to the genus Gorgonolaureus on account of their having an enlarged and inflated carapace with a long, slit-like aperture, long dorsal thoracic horns, no filamentary appendages associated with the first pair of thoracopods, and rudimentary telsonic spines. Gorgonolaureus bicornutus differs from its congeners in having two long, naked dorsal horns on thoracomeres 2 and 3, the number of seminal receptacles in the thoracopods, and the higher number of stout setae on the fifth antennular segment. The characters that unite the genus Gorgonolaureus are redefined as follows: i) the absence of filamentary appendages associated with the first pair of thoracopods; ii) the possession of 1–3 dorsal horns distributed singly among thoracomeres 1–3; iii) the absence of prominent proximal teeth medially on the mandibles; iv) the possession of short or rudimentary telsonic spines; and v) host preference, with most species infecting octocorals of the suborder Halaxonia (mostly of the family Plexauridae) and never the calcaxonian families Chrysogorgiidae and Isididae. The gorgonian-infecting genera Gorgonolaureus and Isidascus are Tethyan relics that have survived only in the Western Pacific and the Eastern Atlantic, respectively, while their relatives in the genera Cardomanica and Thalassomembracis have disjunct Western Atlantic/Western Pacific distributions, thus exemplifying a major pattern of Tethyan reliction.