Ang pangalang ""Malaysia"" ay ginamit noong 1963 nang ang Kalipunan ng Malaya, Singapore, Hilagang Borneo at Sarawak ay bumuo ng isang pederasyong may 14 na estado. Subalit bago mabuo ang pederasyon, ang pangalang ito ay madalang na ginamit upang tukuying ang mga pook sa Timog Silangang Asya. Isang mapa ang inilathala noong 1914 sa Chicago na may nakatalang salitang Malaysia ang nagsasabi sa ilang mga teritoryo sa loob ng Arkipelago ng Malay. Minsan rin inisip ng Pilipinas na gamitin ng kanilang bansa ang pangalang ""Malaysia"", subalit ginamit na ito ng Malaysia noong 1963 bago man gawan ito ng hakbang Pilipinas. Ang iba pang pangalang naisip noon 1963 ay ang Langkasuka, na hango sa dating kaharian na matatagpuan sa hilagagn bahagi ng Tangway ng Malay noong unang sanglibong taon.