History of relations between the two countries can be traced back in 1866 during the Austrian Empire period when the Emperor of Franz Joseph approved the opening of an imperial-royal Honorary Consulate in Penang. However, when the Great Britain declared a war against the Austro-Hungarian Empire in August 1914, the Austrian Consulate was closed down and the last Austrian consul in Penang was detained and deported to Australia by the British administration.
Another related history is located on the island of Borneo when the Austrian Consul in Hong Kong gets the territory of North Borneo after being sold from an American trading base in Hong Kong. Baron von Overbeck managed to get a 10-year renewal for the lease of the territory from the Temenggong of Brunei, and a similar treaty from the Sultanate of Sulu on 22 January 1878. To finance his plans for the territory, von Overbeck gets a financial backing from the Dent brothers (Alfred and Edward). However, after a high effort to promote the territory to the Austrian government, he was unable to get any attention by his government to conquer the territory. Overbeck later withdrew in 1880, leaving it to Alfred Dent to manage the territory.
The Austrian make a first formal diplomatic relations on 6 August 1962. In 1967, Austria established its Honorary Consulate in Kuala Lumpur and between 1973–1974, both the Austrian Embassy in Kuala Lumpur and Malaysian Embassy in Vienna were opened.
In 2005, Malaysia and Singapore was the main trade partner for Austria, with Malaysia became Austria's most important partner in Southeast Asia. Austria main investment in Malaysia are mostly in energy and natural resources sector. In 2009, the financial crisis make an impact to the trade relations with a decreased by 30% but later improved after the visit of the Austrian President Heinz Fischer in 2011. Since 1976, several agreements has been signed between the two countries.
- "Austrian Embassy Kuala Lumpur". The Austrian Foreign Ministry. Retrieved 24 May 2014.
- "Official Website of Embassy of Malaysia, Vienna". Ministry of Foreign Affairs, Malaysia. Retrieved 24 May 2014.
- "Austria-Malaysia (Bilateral Relations)". The Austrian Foreign Ministry. Retrieved 24 May 2014.
- Rozan Yunos (21 September 2008). "How Brunei lost its northern province". The Brunei Times. Archived from the original on 23 May 2014. Retrieved 24 May 2014.
- Rozan Yunos (7 March 2013). "Sabah and the Sulu claims". The Brunei Times. Archived from the original on 23 May 2014. Retrieved 24 May 2014.
- "Our History". Ministry of Foreign Affairs, Malaysia. Retrieved 24 May 2014.
- Reinhart Zimmermann (2008). "Österreichs Wirtschaftsbeziehungen in Südostasien (Austrian Economic Relations to South-East Asia)" (PDF) (in German). Society for South-East Asian Studies. p. 80. Retrieved 24 May 2014.
- "Bilaterale Staatsverträge (Österreich - Malaysia)" (in German). The Austrian Foreign Ministry. Retrieved 24 May 2014.