Coastal blue carbon habitats, including mangroves, seagrasses, and saltmarshes, store carbon and provide important co-benefits such as coastal protection, water filtration, and habitat for biodiversity. Blue carbon sequestration (via restoration and conservation of coastal habitats) is a potential nature-based solution to climate change. In Australia, the blueCAM methodology has been ratified by the Clean Energy Regulator, though at present there is no counterpart in New Zealand. However, the new Government in New Zealand has confirmed support for blue carbon and have recognised that “coastal forests” (i.e., blue carbon habitats) should be eligible for government carbon credits, as land-based forests currently do. Here we discuss the current spatial opportunity for coastal blue carbon in NZ at present and under climate change. We explore what lessons can be learned from Australia’s first blue carbon projects and summaries what challenges remain in New Zealand to move forward similarly.