The advisory, which appeared Sunday, cautions Australians to be vigilant, saying attacks could occur in locations frequented by Westerners or target Western interests.
In response to Australia's warning, a spokesman for Malaysia's Foreign Ministry said there was "nothing to be alarmed of"."We also acknowledge the fact that foreign missions are at liberty to provide their own assessment of the security situation in their host countries," said the spokesman, adding "it may not be accurate or give a true reflection of the situation".
Australia's announcement follows the British government's advisory last week that changed its terrorism threat level for Malaysia from general to high.
Australia, Britain, Canada and New Zealand earlier warned their citizens against travelling to the coastal islands of east Sabah over risks of kidnapping.
Kidnapping for ransom of Malaysians and foreigners in Sabah by militant groups from the southern Philippines has occurred since 2000. New Zealand has a "high risk" alert for travel to the area.
Australia's new advisory also has a note asking citizens to avoid going to resorts, dive sites and tourist facilities in the coastal area of east Sabah. The note says the risk of kidnapping increases on the water and on waterfronts after nightfall.
Singaporean Sean Yang, 37, who works in the finance sector and travels to Kuala Lumpur often, said big cities run the risk of terrorist attacks. "As an individual, if you stay clear of touristy and crowded areas, you can minimize some of that risk."Malaysian police have arrested over 100 people suspected to have links with Islamic State in Iraq and Syria (ISIS) militants since 2014. The most recent arrests took place last month.
Malaysian police have been on the highest alert since last month's terror attack in Jakarta. -