The number of deep-water (>80 m) octocoral species recorded from Australian waters has more than tripled from 135 to 457 following six surveys undertaken between 1997 and 2008 on the deep continental margin of south-eastern, western and north-western Australia and the Tasman Sea.  This rapid increase in knowledge follows a slow accumulation of records since the earliest collections were made by vessels such as the Géographe and the Naturaliste in the early years of the 19th century. Consistent identification and alpha-labelling of the octocoral fauna between surveys has permitted a multi-region description and comparison.  We detail the identities, distributions and regional affinities of 457 octocoral species in 131 genera and 28 families from the orders Alcyonacea and Pennatulacea, including 69 new species, 17 new genera and 43 first records for Australia. Five of the more common genera were widely distributed (present at 35 and 66 sampling stations spanning all of the 4 survey regions), but two were restricted to south-eastern Australia—Pleurogorgia Versluys, 1902 and Tokoprymno Bayer, 1996—and were only sampled from depths below 700 m.  The great majority of species (81%) and nearly half of all genera (47%) were only sampled once or twice.  The highest average number of species per sampling station (3.2) was reported from the outer shelf. The proportion of new species was highest (>22%) on the upper and lower slope bathomes, intermediate (13–15%) on the mid-slope bathome and lowest (8%) on the outer shelf bathome.  Species overlap between bathomes was low, but all families were shared across bathomes. Most described species (55 of 69) have an Indo-West Pacific affinity, 20 have an Indian Ocean affinity, while three were previously recorded from the Atlantic Ocean only; 20 appear to be Australian endemics. Octocorals can now be added to an emerging set of taxon-specific data sets—including fishes, ophiuroids and galatheids—that permit regional-scale analysis of biodiversity distributions to support Australia’s efforts in marine conservation management. However, because so much of the world octocoral literature is inadequate for accurate identifications to species level, there is a pressing need for taxonomic revisions using modern morphological and molecular techniques to fine-tune the current use of octocorals as indicators of vulnerable marine ecosystems in many national and high seas conservation initiatives.