During the excavation of Mayan tombs, little did the archaeologists know that the fossils they discovered in the tomb stones would fundamentally alter our understanding of the earliest origins of coral reef fishes. Located just 500 km from the point where an asteroid impact reconfigured the world’s biological systems 66 million years ago, we find the earliest origins of three typical reef fish groups. Their presence in Mexico just three million years after this impact finally reconciles the conflict between the fossil and phylogenetic evidence for the earliest origins of reef fishes. The incorporation of these fossils into a global reconstruction of fish evolutionary history reveals a new picture of the early biogeography of reef fishes, with strong Atlantic links. From locations associated with biological destruction and societal collapse, we see evidence of the origins of one of the world’s most diverse and spectacular marine ecosystems: coral reefs.