Black corals (Anthozoa: Antipatharia) occur in all the world’s oceans in a wide range of habitats from shallow-water coral reefs to the deep-sea. However, the taxonomy of black corals is poorly known compared to many other anthozoan groups. This knowledge gap is particularly acute for the deep-sea, where collecting specimens is logistically difficult and costly. Here, we identify 21 black coral specimens collected from the western Coral Sea adjacent to north-east Australia. The specimens represent five nominal species from five genera and two families. All species represent new records for the region, including the first record for the family Cladopathidae Brook, 1889. We describe the morphology of these specimens, note geographic and bathymetric range expansions, and provide evidence to support the hypothesis that Bathypathes seculata Opresko, 2005 is the juvenile stage of Bathypathes patula Brook, 1889, thus warranting synonymization. Our findings demonstrate that deep-sea antipatharians in this region are much more diverse than previously reported. Furthermore, this study highlights the importance of museum collections in terms of increasing our understanding of taxonomy and patterns of biodiversity, particularly for poorly-studied habitats such as the deep-sea.