Coral reef based tourism in the Coral Triangle region is responsible for economic benefits but also for negative social and environmental impacts, thus an approach to evaluate this industry's sustainability performance would be valuable. We selected 10 key indicators, out of 681, that were directly relevant to the impacts of tourist activities on coral reefs in economic, social, environmental, and wildlife aspects of sustainability. Efficiency, inefficiency and overall models were developed to measure relative sustainability performance focusing on coral reef protection by the tourism industry for all six countries in the Coral Triangle, from 2008 to 2012. Our results showed that Indonesia had the best relative performance among countries in the region, followed in descending order by; Papua New Guinea, Malaysia, Philippines, Timor-Leste, and Solomon Islands. Future plans to achieve higher performance by the tourism industry in each country can be made if a comprehensive sensitivity analysis is carried out.