Modern hard corals (Class Hexacorallia; Order Scleractinia) are widely studied because of their fundamental role in reef building and their superb fossil record extending back to the Triassic. Nevertheless, interpretations of their evolutionary relationships have been in flux for over a decade. Recent analyses undermine the legitimacy of traditional suborders, families and genera, and suggest that a non-skeletal sister clade (Order Corallimorpharia) might be imbedded within the stony corals. However, these studies either sampled a relatively limited array of taxa or assembled trees from heterogeneous data sets. Here we provide a more comprehensive analysis of Scleractinia (127 species, 75 genera, 17 families) and various outgroups, based on two mitochondrial genes (cytochrome oxidase I, cytochrome b), with analyses of nuclear genes (ß-tubulin, ribosomal DNA) of a subset of taxa to test unexpected relationships. Eleven of 16 families were found to be polyphyletic. Strikingly, over one third of all families as conventionally defined contain representatives from the highly divergent “robust” and “complex” clades. However, the recent suggestion that corallimorpharians are true corals that have lost their skeletons was not upheld. Relationships were supported not only by mitochondrial and nuclear genes, but also often by morphological characters which had been ignored or never noted previously. The concordance of molecular characters and more carefully examined morphological characters suggests a future of greater taxonomic stability, as well as the potential to trace the evolutionary history of this ecologically important group using fossils.