Population outbreaks of the coral-eating predator crown of thorns starfish (COTS), Acanthaster planci are responsible for large-scale disturbance of coral reefs throughout the Indo-Pacific. In response, attempts are often made to control COTS outbreaks in protected areas. For instance, volunteers remove thousands of sea stars every year in Malaysia. This study reports the status of the COTS population in the Pulau Tioman Marine Park and examines the effectiveness of the seasonal sea star removal programme. After the 2009 removal season, we monitored COTS densities and coral assemblages before and after a 6-month no-removal season at sites with and without COTS removal efforts. We recorded high COTS densities up to 330 ind. ha−1 at a few sites independent of removal effort. In fact, removal only temporarily reduced large individuals from local populations. Moreover, after the no-removal season, sites with COTS removal had increased live coral cover, but sites without COTS removal had a drastic decrease in live coral cover, with Acropora spp. being most affected. Therefore, this study suggests that the current seasonal removals could promote coral health, despite the high density of COTS.