Although corals first appeared in the Cambrian period, 542 million years ago, the stony corals (Scleractinia), appeared approximately 237 million years ago. Scleractinian corals include the corals which make the enormous Great Barrier Reef, but also the cold-water corals which we are interested in. The difference is, cold-water corals do not have algae living in their cells (they are ‘azooxanthellate’), while most tropical corals obtain the majority of their energy from these algae.
The first azooxanthellate coral structures (corals lacking photosynthetic algae) are at least 145 million years old. So far, we know from geological records that Lophelia sp. and some other cold-water coral species appeared at least 23 million years ago. As we keep finding more and more of these fossilized corals, we think that cold-water corals started to become much more widespread from that point onwards.