Scleractinian corals represent the foundation species of one of the most diverse and productive ecosystem on earth, coral reefs. Corals not only constitute the trophic basis of these ecosystems, but also provide essential habitats and shelter for a wide variety of marine species, many of which are commercially relevant. They also provide other important ecosystem services such as food provision, shoreline protection and opportunities for ecotourism. Despite the ecological importance of corals, very little is known about how their soft-bodied ancestor evolved the ability to form a calcified skeleton and became the ecosystem builders they are today. Corallimorpharia are closely related to reef-building corals but lack the ability to form calcified skeletons. Here we assembled and annotated two draft genomes of the corallimorpharians, Amplexidiscus fenestrafer and Discosoma sp., and further provided an online interface to facilitate the use of these resources. The two genomes can not only inform on the current evolutionary gap in genomic resources for the subclass of Hexacorallia but also provide important resources for comparative genomic studies aiming at understanding the evolution of coral specific traits. Our broad phylogenomic approach using whole genome data, including phylogenetic analyses of nuclear encoding genes as well as genome-wide presence/absence information and synteny conservation from six hexacorallian species, provides robust evidence that corallimorpharians are a monophyletic sister group of scleractinians, therefore rejecting the “naked coral” hypothesis. Being the closest non-calcifying relative of scleractinian corals, corallimorpharians appear to be the best candidates to understand the evolutionary origin of coral calcification. Molecular divergence analysis of scleractinian coral and Corallimorpharia genes suggests that the soft-bodied ancestor of corals evolved the ability to calcify within approximately 80 million years after the divergence of these two orders. To uncover the molecular basis of coral skeletal formation and growth, we integrate genomic and transcriptomic data as well as skeletal proteomic data, and show that gene and domain duplications have been the main evolutionary mechanisms underlying the evolution of calcification in scleractinian corals.