In recent decades, extensive mortality of reef-building corals throughout the Caribbean region has led to the erosion of reef frameworks and declines in biodiversity. Using field observations, models, and high-precision U–Th dating, we quantified changes in the structural complexity of coral reef frameworks over the past 2 decades. Structural complexity was stable at reef scales, yet bioerosion led to declines in small-scale microhabitat complexity with cascading effects on cryptic fauna.