A complete taxonomic revision of the genus Anthothela (Anthothelidae) and closely related taxa is presented herein, based on original type material of nominal species and additional specimens from multiple deep-water surveys. A multi-disciplinary approach was used, combining morphological characteristics such as colonial branching patterns, polyp structure, and sclerite form and arrangement, together with phylogenetic reconstructions using two mitochondrial gene regions (mtMutS and igr1–cox1). The genus Anthothela, with seven nominal species globally, is here divided into four genera, two of which are new. Three of the original species of Anthothela are validated (A. grandiflora Sars, 1856, A. pacifica Kükenthal, 1913 and A. tropicalis Bayer, 1961), Spongioderma (?) vickersi Benham, 1928 is reassigned to Anthothela and two new species, A. aldersladei and A. quattriniae, are described. Anthothela argentea Studer, 1894, A. macrocalyx (Nutting, 1911) and A. nuttingi Bayer, 1956 are reassigned to Victorgorgia López-González & Briand, 2002 and two new species of this genus, V. eminens and V. nyahae are described. A new family, Victorgorgiidae is described for Victorgorgia due to clear morphological and genetic differences from Anthothela, the type genus of Anthothelidae. A new genus, Williamsium (Anthothelidae), is described for A. parviflora Thomson, 1916 which is restricted to South African waters. A number of North Atlantic Ocean specimens that have traditionally been mistaken for Anthothela grandiflora were found to be synonymous with Alcyonium grandiflorum (Tixier-Durivault & d'Hondt, 1974) and a second new genus, Lateothela (Anthothelidae), is erected for these specimens based on morphological and molecular evidence that Alcyonium grandiflorum was incorrectly placed in the genus Alcyonium Linnaeus. There is good congruence between morphological characteristics and molecular data at a generic level but at a species level, the degree of congruence was inconclusive as morphological and genetic variation is very low. Anthothela and Lateothela n. gen. are found to be closely related to some nominal Alcyonium species, and the family Anthothelidae and subfamily Anthothelinae are shown to be paraphyletic. These are the first records of Anthothela and Victorgorgia from Australian waters.