Nykyisen Malesian valtion alue oli 800-luvulta 1400-luvulle asti Jaavan ja Sumatran suunnalta tulleiden kuningaskuntien vallan alla. Kun kuningaskunnat rappeutuivat, Malakan niemimaalle syntyi useita pienempiä kuningaskuntia, jotka harjoittivat elinkeinoinaan merenkulkua ja kaupankäyntiä. Huomattavin valtio oli Malakan sulttaanikunta, joka kehittyi tärkeäksi satamakaupungiksi. Malakan niemimaa on jo varhaisista ajoista lähtien sijainnut Kiinan ja Intian välisten kauppareittien varrella, ja maa on historiansa aikana saanut kulttuuriinsa vaikutteita Kiinan, Intian ja Arabian suunnalta.
Eurooppalaiset tulivat alueelle 1500-luvulla ja Malakan sulttaanikunnan valloittivat ensin portugalilaiset ja 1600-luvulla hollantilaiset. Britit saapuivat alueelle 1800-luvulla ja perustivat ensin Singaporen kauppatukikohdan ja yhdistivät sen jälkeen Singaporen, Malakan ja Penangin Salmisiirtokunniksi. 1900-luvulle tultaessa koko nykyisen Malesian alue oli vähitellen siirtynyt brittien hallintaan.
Toisen maailmansodan aikana japanilaiset miehittivät maan. Sodan päätyttyä niemimaan sulttaanikunnat yhdistettiin vuonna 1946 Malaijan liitoksi, joka muutettiin vuonna 1948 Malaijan federaatioksi. Britannia myönsi Malaijalle itsenäisyyden vuonna 1957. Vuonna 1963 Malaijaan liitettiin Singapore, Sarawak ja Pohjois-Borneo, samalla valtion nimeksi tuli Malesian liittovaltio. Singaporen ja Malesian valtioliitto purettiin jo kahden vuoden kuluttua, syynä olivat jännitteet Malesian malaijiväestön ja Singaporen kiinalaisväestön välillä.
1980-luvulla Malesia alkoi modernisoitua ja teollistua Mahathir Mohamadin johdolla. Malesia muuttui raaka-aineiden viejästä teollisuuden ja valmistuksen keskukseksi, houkutellen ulkomaisia investointeja ja parantaen infrastruktuuria.
Esihistoria Varhaisin todiste asutuksesta Borneolla on Sarawakin osavaltion alueella olevan Niahin kansallispuiston luolista löydetty ihmisen pääkallo, joka on radiohiiliajoituksen perusteella noin 40 000 vuotta vanha. Malakan niemimaalta löytyneet vanhimmat ihmisasutuksen merkit ovat noin 10 000 vuoden takaa. Tuolla ajanjaksolla orang asli -alkuasukasheimojen elinalue levisi pohjoisesta niemimaan eteläosiin. Ensimmäinen muuttoaalto Malakan niemimaalle saapui nykyisen Etelä-Kiinan alueelta noin 3000 eaa. Alueen varhaiset asukkaat olivat metsästäjä-keräilijöitä, ja heitä kutsutaan protomalaijeiksi.
Noin vuonna 300 eaa. alueelle saapui deuteromalaijeja ja protomalaijit siirtyivät heidän tieltään sisämaahan. Orang asli -alkuasukasheimoja elää edelleen maan sademetsäalueen reservaateissa. Deuteromalaijeja pidetään nykyisten malaijien kantaisinä. Deuteromalaijit asettuivat rannikoille ja jokien varsiin, ja he solmivat kauppasuhteita Kiinan ja Intian suunnalta tulleiden kauppiaiden kanssa. Intian ja Kiinan väliset kauppalaivat kulkivat Malakansalmea pitkin ja näin malaijikansat saivat vaikutteita kiinalaisista ja intialaisista kulttuureista. Ajanlaskun alussa hindulaisuus ja buddhalaisuus levisivät Malesian alueelle. Levittäjinä olivat nykyisen Intian alueella sijainneesta Pallavan kuningaskunnasta tulleet kauppiaat. Myös sanskritin kirjoitusjärjestelmä omaksuttiin 400-luvulla.
Varhaiset kuningaskunnat Srivijaya thumb|right|Kedukan Bukitin piirtokirjoitus vuodelta 683 on vanhin säilynyt srivijayalainen piirtokirjoitus Malakan niemimaalla oli 300–400-luvulla kolmisenkymmentä varhaista kuningaskuntaa, jotka sijaitsivat pääosin maan itäosissa. Malaijilaisten kirjoitusten mukaan Gangga Negaran hindukuningaskunta sijaitsi nykyisen Perakin alueella. Ajankohdasta ei ole varmuutta, mutta sen epäillään olleen olemassa 200–1100-luvulla. Kelantanin tai Terengganun osavaltion alueella uskotaan sijainneen 300–500-luvuilla Pan Panin kuningaskunta. Muinaisen Langkasukan kuningaskunta sijaitsi 200-luvulta aina 1400-luvulle asti nykyisen Malesian pohjoisosassa ja Thaimaan eteläosassa. 600-luvulla myös nykyisen Kambodžan alueella sijainnut Funanin kuningaskunta hallitsi niemimaan itäosia.
Malaijien ensimmäinen merkittävä kauppaa harjoittanut kuningaskunta oli Sumatralta lähtöisin ollut Srivijaya, joka hallitsi 700-luvulta lähtien Malakansalmen laivaliikennettä ja merkittävää osaa niemimaan eteläosasta. Srivijayan mukana Malakan niemimaalle levisi myös malaijin kieli. Srivijayan valtakunnan vaikutusalue ulottui laajimmillaan muidenkin varhaisten kuningaskuntien alueelle. Srivijayan pääkaupunki oli Sumatralla sijaitseva Palembang, ja epäillään että maalla oli valtakeskus Malakan niemimaalla Kedahin alueella tai eteläisen Thaimaan alueella.
Shrivijaya kohtasi 1000-luvun alussa ulkoisia uhkia, kun Jaavan ja Intian kuningaskunnat yrittivät horjuttaa sen valta-asemaa. Intialainen Chola-dynastia sai Malakan niemimaan haltuunsa vuonna 1025 noin 20 vuoden ajaksi. Chola valloitti 1068 Kedahin Srivijayalta lopullisesti. Chola ei saanut koko Shrivijayan valtakuntaa haltuunsa, mutta valtakunta heikkeni niin paljon, että sen vaikutusalueelle alkoi muodostua pienempiä kuningaskuntia, kuten Kedirin kuningaskunta Jaavalle. Shrivijaya jakoi 1100-luvulla valta-asemansa Kedirin kanssa Malaijien saaristossa. Shrivijaya hallitsi länsiosia ja Malakan niemimaan aluetta ja Kediri saariston itäosia.
Srivijayan voimakas vaikutus alueella alkoi hiipua 1200-luvulla. Valtakunnalla oli toistuvasti konflikteja jaavalaisten kuningaskuntien kanssa, joille se jäi alakynteen. Pääsyynä valtakunnan murenemiseen oli sen kauppavallan heikkeneminen. Valta jakautui tasaisemmin alueen pienemmille keskuksille, kuten Shrivijayasta irtautuneelle Jambille ja Kedahin satamalle.
Singhasari ja Majapahit Vuonna 1288 Kedirin kuningaskunnan valtaansa alistanut Singhasari valloitti Shrivijayalta Malakan niemimaan itä- ja eteläosat sekä Sumatralla sijainneita alueita. Singhasarin valtakausi ei kestänyt kauan, sillä mongolit saapuivat 1270-luvulla Kiinan alueelle. Kublai-kaanin johtaman mongolien Yuan-dynastian lähettiläät saapuivat Kiinasta Kaakkois-Aasiaan ja vaativat jaavalaisilta vasalliveron maksamista. Tähän ei Singhasarin hallitsija Kertanagara suostunut, vaan lähetti mongolien lähetystön takaisin. Kublai-kaani kokosi suuren laivaston jaavalaisten rankaisemiseksi, mutta ennen mongolien hyökkäystä Kertanagara murhattiin vuonna 1292 Kedirin kapinoidessa Singhasaria vastaan.
Shrivijayan uusi kuningas Kertarajasa, Kertanegaran vävy, pakeni Kedirin kapinaa Majapahitiin, mihin hän perusti uuden pääkaupungin. Kertarajasa liittoutui mongolien kanssa 1293 Kedirin kukistamiseksi. Kun Kedirin joukot oli kukistettu, Kertarajasan johtamat majapahijoukot tekivät yllätyshyökkäyksen mongoleja vastaan ja karkottivat heidät juuri syntyneestä Majapahitin valtakunnasta. Näin myös nykyinen Malakan niemimaan alue päätyi Majapahitien hallintaan. Myös pohjoisesta tullut Ayutthayan kuningaskunta valtasi hallintaansa Shrivijayan entisten vasallimaiden alueita.
Majapahitin kuningaskunta hallitsi 1300-luvulla suurinta osaa nykyisestä Malesiasta ja Indonesiasta. Vuonna 1377 Majapahitin laivasto valloitti myös Palembangin, joka oli viimeisiä jäänteitä Shrivijayan valtakunnasta. Palembangin prinssi Paramesvara kapinoi Majapahitin hallintoa vastaan perustamalla uuden valtakeskuksen Malakan niemimaalle. Hän pakeni Majapahitin valloituksia Temasekin, nykyisen Singaporen saarelle. Hän perusti Temasekiin uuden valtakeskuksen syrjäytettyään sen hallitsijan, mutta saari osoittautui liian turvattomaksi. Vuonna 1398 Paramesvara pakeni Temasekista ja yritti perustaa uuden tukikohdan Malakaan.
Majapahitin valtakausi alueella ei kestänyt kauan. Valtakunnan viimeisimmän pääministerin Gajah Madan kuoltua vuonna 1364 maa alkoi rapistua. 1400-luvun alussa maa ajautui sisällissotaan ja sen hallitsemat alueet alkoivat itsenäistyä. Myös Malakan niemimaan alueelle muodostui useita pieniä sulttaanikuntia ja kaupunkivaltioita, jotka harjoittivat elinkeinoinaan kauppaa ja merenkulkua.
Malakan sulttaanikunta Sumatralta ja Temasekista paennut prinssi Paramesvara perusti vuonna 1402 Malakansalmen länsirannikolle Malakan sulttaanikunnan. Kapinoidessaan Majapahitien valloituksia vastaan Paramesvara loi hyvät suhteet kiinalaisiin, ja Malakan sulttaanikunta pääsi Kiinan Ming-dynastian keisarin suojelukseen. Malakka kasvoi nopeasti kiinalaisten suojeluksessa alueen merkittävimmäksi satamakaupungiksi. Malakan niemimaan alueelle muodostui ensimmäistä kertaa poliittista yhtenäisyyttä, mitä pidetään myös nykyisen Malesian historiassa kansakunnan alkuna.
Islam saapui alueelle alun perin arabialaisten ja Pohjois- ja Etelä-Intiasta tulleiden muslimikauppiaiden mukana. Sulttaanikunnan alkuvuosina myös kuningas Paramesvara omaksui islaminuskon ja otti käyttöön nimen Iskandar Shah. Samalla Malakan alun perin hindulais-buddhalainen kuningaskunta muuttui sulttaanikunnaksi, koska sulttaani on islamilainen arvonimi hallitsijalle. Islamista oli myös kaupallista hyötyä, sillä arvonimi sulttaani erotti Malakan alueen aiemmista hallitsijoista. Sulttaanikuntaan saatiin helpommin houkuteltua muslimikauppiaita Persian ja Intian suunnalta. Poliittisen vallan ansiosta Malakasta käsin islamia levitettiin myös muualle Kaakkois-Aasiaan.
Sijaintinsa ansiosta Malakka pystyi hallinnoimaan Kiinan ja Intian välistä kauppamerenkulkua, josta tuli yhä merkittävämpää, sillä 1400-luvulla merireitit korvasivat mongolien hallitseman silkkitien Kiinan ja Lähi-idän ja Euroopan välillä. Monsuunituulet pitivät välillä kauppa-aluksia Malakan satamassa useiden kuukausien ajan, minkä vuoksi kaupunki oli täynnä ulkomaalaisia kauppiaita. Malakka oli merkittävä kangaskaupan keskus, ja kaupunkiin tuotiin runsaasti riisiä Jaavasta, Burmasta ja Ayutthayasta, koska Malakassa ei ollut tarpeeksi omaa ruoantuotantoa. Malakka kasvoi 1400-luvulla alueen tärkeimmäksi ja vauraaksi kaupan keskukseksi. Malakan sulttaanikunta hallitsi suurta osaa nykyisestä Malakan niemimaasta ja nykyisestä Indonesiasta.
Malakan sulttaanikunnan valtakausi kesti hieman yli sata vuotta. Tällä ajanjaksolla luotiin malaijikulttuurin keskus, ja ajanjaksolta ovat peräisin myös monet tulevat sulttaanikunnat. Malakasta tuli kulttuurikeskus, jossa on nykyäänkin jäljellä kiinalaisten, intialaisten ja muslimien kulttuuriperinteitä. Malaijin kieli muodostui alueen valtakieleksi.
Siirtomaavallan alku Portugalin valtakausi thumb|A Famosan linnoituksen raunioita Malakassa. Malakan sulttaanikunnan vauraus houkutteli alueelle myös eurooppalaisia. Ottomaanien valtakunta sulki eurooppalaisten maareitin Kiinaan ja Intiaan, mikä ajoi eurooppalaisia etsimään merireittiä Kaukoitään. 1500-luvulle asti Malakalla oli valta-asema Kaakkois-Aasian kansainvälisenä markkinapaikkana. Portugalilaiset pyrkivät 1500-luvun alussa saamaan itselleen monopoliaseman maustekaupassa. Vuonna 1510 Portugali valloitti Goan, johon Afonso de Albuquerque perusti tukikohdan. Goalta käsin suunniteltiin Malakan valloitusta. Albuquerquen johtamat portugalilaiset hyökkäsivät 1511 Malakan sulttaanikuntaan. Eurooppalaiset olivat raskaammin aseistettuja, ja heidän aluksensa olivat nopeampia ja suurempia kuin aasialaisten alukset. Myös malaijeilla oli raskaita tykkejä, joita käytettiin portugalilaisia valloittajia vastaan. Portugalilaiset kokivat taistelussa huomattavia tappioita, ja Malakka kukistui vasta kuukauden mittaisen kiivaan meri- ja maataistelun jälkeen. Malakan kukistuttua Malakan sulttaani pakeni niemimaan eteläosiin, mihin hän perusti Johoren sulttaanikunnan.
Malakan valloituksen jälkeen Malakasta kehittyi Portugalin hallintokeskus Kaakkois-Aasiassa, ja maa sai hallintaansa Malakansalmen. Malakkaan rakennettiin A Famosan linnoitus ja hallintorakennuksia, joista portugalilaiset hallinnoivat Aasian kauppaansa ja Malakan ohella valloittamiaan Maustesaaria. Portugalilaiset toivat mukanaan katolisuuden, ja kaupunkiin rakennettiin uskonnollisia rakennuksia kristinuskon levittämiseksi.