Adaptive radiations have been instrumental in generating a considerable amount of life’s diversity. Ecological opportunity is thought to be a prerequisite for adaptive radiation, but little is known about the relative importance of species’ ecological versatility versus effects of arrival order in determining which lineage radiates. Palaeontological records that could help answer this are scarce. In Lake Victoria, a large adaptive radiation of cichlid fishes evolved in an exceptionally short and recent time interval. We present a rich continuous fossil record extracted from a series of long sediment cores along an onshore–offshore gradient. We reconstruct the temporal sequence of events in the assembly of the fish community from thousands of tooth fossils. We reveal arrival order, relative abundance and habitat occupation of all major fish lineages in the system. We show that all major taxa arrived simultaneously as soon as the modern lake began to form. There is no evidence of the radiating haplochromine cichlid lineage arriving before others, nor of their numerical dominance upon colonization; therefore, there is no support for ecological priority effects. However, although many taxa colonized the lake early and several became abundant, only cichlids persisted in the new deep and open-water habitats once these emerged. Because these habitat gradients are also known to have played a major role in speciation, our findings are consistent with the hypothesis that ecological versatility was key to adaptive radiation, not priority by arrival order nor initial numerical dominance.