Abstract Tun Mustapha Park, in Sabah, Malaysia, was gazetted in May 2016 and is the first multiple-use park in Malaysia where conservation, sustainable resource use and development co-occur within one management framework. We applied a systematic conservation planning tool, Marxan with Zones, and stakeholder consultation to design and revise the draft zoning plan. This process was facilitated by Sabah Parks, a government agency, and WWF-Malaysia, under the guidance of the Tun Mustapha Park steering committee and with support from the University of Queensland. Four conservation and fishing zones, including no-take areas, were developed, each with representation and replication targets for key marine habitats, and a range of socio-economic and community objectives. Here we report on how decision-support tools informed the reserve design process in three planning stages: prioritization, government review, and community consultation. Using marine habitat and species representation as a reporting metric, we describe how the zoning plan changed at each stage of the design process. We found that the changes made to the zoning plan by the government and stakeholders resulted in plans that compromised the achievement of conservation targets because no-take areas were moved away from villages and the coastline, where unique habitats are located. The design process highlights a number of lessons learned for future conservation zoning, which we believe will be useful as many other places embark on similar zoning processes on land and in the sea.