Coral reefs face threats from climate change and local pressures that lead to reductions in their physical structure, impacting biodiversity by limiting habitat availability. Despite many efforts to actively restore damaged reefs, few projects provide thorough evaluations of their success. This study measured the success of the “Reef Star” method at the Mars Coral Reef Restoration Project in Indonesia in reestablishing the physical structure of reef habitats that were destroyed by blast fishing. We used photogrammetry surveys to measure the physical habitat structure of 17 large sites (1000 m2 each), calculating three complementary measures of small- and large-scale habitat complexity across degraded, restored, and naturally healthy coral reefs. We demonstrate that the restoration efforts have successfully restored small-scale habitat complexity, as described by surface complexity metrics (3.22 ± 0.27 on restored reefs; 2.85 ± 0.26 on healthy reefs) and fractal dimension (2.27 ± 0.02 on restored reefs; 2.24 ± 0.02 on healthy reefs). This demonstrates the capacity for restored reefs to recover important ecosystem functions that are lost in degradation. However, while restoration has delivered some increases in large-scale habitat complexity compared to degraded reefs, restored reefs still exhibit lower values of maximum vertical relief than healthy reefs, due to a lack of large physical structures. This lack of available large-scale habitat might impact fish populations, meaning that restored reefs with limited large-scale complexity may only support a restricted range of ecosystem functions. Effective reef restoration strategies must use a mixture of different methods that target the recovery of structural complexity at multiple scales.