The assessment was made after a study conducted between April and June, it said in a statement Sunday.
Severe or prolonged heat stress leads to corals dying off, though there is a possibility for recovery if temperatures drop and other stressors such as overfishing and pollution are reduced.
The department urged tour operators to control the number of tourists involved in recreation activities to reduce pressure on reefs.
"If bleaching is greater than 80%, further management interventions may include temporary access restrictions to protect affected reefs," it said.
It added that it was setting up a coral bleaching response committee with researchers, NGOs and representatives from the states of Sabah and Sarawak on Borneo island.
The Southeast Asian country has many popular diving spots and a rich and vibrant marine life, with waters around 42 islands gazetted as marine parks.
Coral around the world is struggling with mass bleaching events that scientists warn are expanding and deepening.
Record ocean temperatures have caused parts of reefs in 62 countries and territories to turn ghostly white as they expel the algae that live inside them.
Corals live in a symbiotic relationship with the microscopic zooxanthellae algae, which produce food and give the reef its color.
Without the algae, the reef turns white, and if temperatures don't fall, the coral will die.
The consequences of coral bleaching are far-reaching, affecting not only the health of oceans but also the livelihoods of people, food security and local economies.