Structural complexity created by biogenic organisms can support very high biodiversity, exemplified on coral reefs. As ocean warming drives range shifts, many tropical and sub-tropical species are moving increasingly into temperate habitats. On the east coast of Australia, the subtropical endemic coral Pocillopora alicia seems to be growing rapidly in barrens habitat in the Sydney region. Given the often tight association between the structure provided by habitat formers and their associated assemblages, this novel creation of habitat formers raises import questions about how the provision of different types of habitat may change in a warming ocean. Here we use high resolution large-area 3D mapping and novel characterisations of the elements of structural complexity to compare the structural environment of areas across this transition zone from tropical to temperate benthic marine habitats along the East Coast of Australia (Great Barrier Reef to Sydney, NSW). The results suggest that the increase in abundance of P. alicia in temperate habitats has the potential to provide novel elements of structural complexity to these reefs, especially at small spatial scales. This work raises important questions about the amounts and types of organisms that such novel coral habitat may host in temperate regions in the future.