The exploration of Earth's biodiversity is an exciting and ongoing endeavour. Here, we report a new species of seadragon from Western Australia with substantial morphological and genetic differences to the only two other known species. We describe it as Phyllopteryx dewysea n. sp. Although the leafy seadragon (Phycodurus eques) and the common seadragon (Phyllopteryx taeniolatus) occur along Australia's southern coast, generally among relatively shallow macroalgal reefs, the new species was found more offshore in slightly deeper waters. The holotype was trawled east of the remote Recherche Archipelago in 51 m; additional specimens extend the distribution west to Perth in 72 m. Molecular sequence data show clear divergence from the other seadragons (7.4–13.1% uncorrected divergence in mitochondrial DNA) and support a placement as the sister-species to the common seadragon. Radiographs and micro-computed tomography were used on the holotype of the new species and revealed unique features, in addition to its unusual red coloration. The discovery provides a spectacular example of the surprises still hidden in our oceans, even in relatively shallow waters.