Over the last half century, climate change, coral disease, and other anthropogenic disturbances have restructured coral-reef ecosystems on a global scale. The disproportionate loss of once-dominant, reef-building taxa has facilitated relative increases in the abundance of “weedy” or stress-tolerant coral species. Although the recent transformation of coral-reef assemblages is unprecedented on ecological timescales, determining whether modern coral reefs have truly reached a novel ecosystem state requires evaluating the dynamics of reef composition over much longer periods of time. Here, we provide a geologic perspective on the shifting composition of Florida's reefs by reconstructing the millennial-scale spatial and temporal variability in reef assemblages using 59 Holocene reef cores collected throughout the Florida Keys Reef Tract (FKRT). We then compare the relative abundances of reef-building species in the Holocene reef framework to data from contemporary reef surveys to determine how much Florida's modern reef assemblages have diverged from long-term baselines. We show that the composition of Florida's reefs was, until recently, remarkably stable over the last 8000 yr. The same corals that have dominated shallow-water reefs throughout the western Atlantic for hundreds of thousands of years, Acropora palmata, Orbicella spp., and other massive coral taxa, accounted for nearly 90% of Florida's Holocene reef framework. In contrast, the species that now have the highest relative abundances on the FKRT, primarily Porites astreoides and Siderastrea siderea, were rare in the reef framework, suggesting that recent shifts in species assemblages are unprecedented over millennial timescales. Although it may not be possible to return coral reefs to pre-Anthropocene states, our results suggest that coral-reef management focused on the conservation and restoration of the reef-building species of the past, will optimize efforts to preserve coral reefs, and the valuable ecosystem services they provide into the future.