The availability of habitat structure across spatial scales can determine ecological organization and resilience. However, anthropogenic disturbances are altering the abundance and composition of habitat-forming organisms. How such shifts in the composition of these organisms alter the physical structure of habitats across ecologically important scales remains unclear. At a time of unprecedented coral loss and homogenization of coral assemblages globally, we investigate the inherent structural complexity of taxonomically distinct reefs, across five ecologically relevant scales of measurement (4–64 cm). We show that structural complexity was influenced by coral species composition, and was not a simple function of coral cover on the studied reefs. However, inter-habitat variation in structural complexity changed with scale. Importantly, the scales at which habitat structure was available also varied among habitats. Complexity at the smallest, most vulnerable scale (4 cm) varied the most among habitats, which could have inferences for as much as half of all reef fishes which are small-bodied and refuge dependent for much of their lives. As disturbances continue and species shifts persist, the future of these ecosystems may rely on a greater concern for the composition of habitat-building species and prioritization of particular configurations for protection of maximal cross-scale habitat structural complexity.