Coral reefs are renowned for their spectacular biodiversity and the close links between fishes and corals. Despite extensive fossil records and common biogeographic histories, the evolution of these two key groups has rarely been considered together. We therefore examine recent advances in molecular phylogenetics and palaeoecology, and place the evolution of fishes and corals in a functional context. In critically reviewing the available fossil and phylogenetic evidence, we reveal a marked congruence in the evolution of the two groups. Despite one group consisting of swimming vertebrates and the other colonial symbiotic invertebrates, fishes and corals have remarkably similar evolutionary histories. In the Paleocene and Eocene [66-34 million years ago (Ma)] most modern fish and coral families were present, and both were represented by a wide range of functional morphotypes. However, there is little evidence of diversification at this time. By contrast, in the Oligocene and Miocene (34-5.3 Ma), both groups exhibited rapid lineage diversification.There is also evidence of increasing reef area, occupation of new habitats, increasing coral cover, and potentially, increasing fish abundance. Functionally, the Oligocene-Miocene is marked by the appearance of new fish and coral taxa associated with high‐turnover fast-growth ecosystems and the colonization of reef flats. It is in this period that the functional characteristics of modern coral reefs were established. Most species, however, only arose in the last 5.3 million years (Myr; Plio-Pleistocene), with the average age of fish species being 5.3 Myr, and corals just 1.9 Myr. While these species are genetically distinct, phenotypic differences are often limited to variation in colour or minor morphological features. This suggests that the rapid increase in biodiversity during the last 5.3 Myr was not matched by changes in ecosystem function. For reef fishes, colour appears to be central to recent diversification. However, the presence of pigment patterns in the Eocene suggests that colour may not have driven recent diversification. Furthermore, the lack of functional changes in fishes or corals over the last 5 Myr raises questions over the role and importance of biodiversity in shaping the future of coral reefs.