Mangrove loss and degradation have triggered global restoration efforts to support biodiversity and ecosystem services, including fish stock enhancement. As mangrove restoration accelerates, it is important to evaluate outcomes for species that play functional roles in ecosystems and support services, yet this remains a clear knowledge gap. There is remarkably little information, for example, about how fish use of mangroves varies as restored vegetation matures, limiting the theoretical links that can be made between restoration and fish stock enhancement. We used unbaited underwater cameras within two distinct zones of mangrove forests – fringe and interior – at five pairs of restored-natural mangrove sites in southeast Queensland, Australia. We used deep learning to automatically extract data for the four commonest species: yellowfin bream (Acanthopagrus australis), sea mullet (Mugil cephalus), common toadfish (Tetractenos hamiltoni) and common silverbiddy (Gerres subfasciatus). The relative abundance of all species (i.e., restored relative to paired natural) was highly variable among sites and zones. Despite younger restored sites having much lower structural complexity, we discovered no trend of greater fish abundance within more mature restored mangroves. In fact, silverbiddy show the opposite with greater relative abundance at younger sites. Further, yellowfin bream and sea mullet were more abundant in the fringe zone, and we observed similarities in how fish used fringe and interior zones across all sites. Our paired, space-for-time design provides a powerful test of restoration outcomes for fish, highlighting that even newly restored sites with immature vegetation are readily utilised by several species.