Indonesia, the most mangrove-rich nation in the world, has proposed the most globally ambitious mangrove rehabilitation target (600,000 ha) of any nation, to be achieved by 2024 to support multiple Sustainable Development Goals (SDG 1–3, 6, 13 and 14). Yet, mangrove restoration and rehabilitation across the world have often suffered low success rates and been applied at small scales. Here, we identify 193,367 ha (estimated costs at US$0.29–1.74 billion) that have the potential to align with the national mangrove rehabilitation programme. Despite being only 30% of the national target, our robust assessment considered biogeomorphology, 20 years of land-use and land-cover change and state forest land status, all key factors moderating mangrove restoration success which have often been neglected in Indonesia. Increasing subnational government representation in mangrove governance as well as improving monitoring and evaluation will increase the likelihood of achieving the mangrove rehabilitation targets and reduce risks of failure. Rehabilitating and conserving mangroves in Indonesia could benefit 74 million coastal people and can potentially contribute to the national land-sector emissions reduction of up to 16%.