Living reef fishes are one of the most diverse vertebrate assemblages on Earth. Despite its prominence and ecological importance, the origins and assembly of the reef fish fauna is poorly described. A patchy fossil record suggests that the major colonization of reef habitats must have occurred in the Late Cretaceous and early Palaeogene, with the earliest known modern fossil coral reef fish assemblage dated to 50 Ma. Using a phylogenetic approach, we analysed the early evolutionary dynamics of modern reef fishes. We find that reef lineages successively colonized reef habitats throughout the Late Cretaceous and early Palaeogene. Two waves of invasion were accompanied by increasing morphological convergence: one in the Late Cretaceous from 90 to 72 Ma and the other immediately following the end-Cretaceous mass extinction. The surge in reef invasions after the Cretaceous-Palaeogene boundary continued for 10 Myr, after which the pace of transitions to reef habitats slowed. Combined, these patterns match a classic niche-filling scenario: early transitions to reefs were made rapidly by morphologically distinct lineages and were followed by a decrease in the rate of invasions and eventual saturation of morphospace. Major alterations in reef composition, distribution and abundance, along with shifts in climate and oceanic currents, occurred during the Late Cretaceous and early Palaeogene interval. A causal mechanism between these changes and concurrent episodes of reef invasion remains obscure, but what is clear is that the broad framework of the modern reef fish fauna was in place within 10 Myr of the end-Cretaceous extinction.