Территория современной Малайзии была заселена уже в раннем палеолите. Древнейшим населением были негро-австралоидные племена. В 3-1 тыс. до н. э. из юго-западного Китая на полуостров Малакка пришли австронезийские племена. В начале 1 тыс. н. э. на территорию современной Малайзии из районов центральной Суматры начинают проникать предки современных малайцев.

Первые государства (Ланкасука, Тамбралинга, Такола, Кедах и другие) возникли на севере полуострова Малакка, на пересечении торговых путей из Индии в Китай. Значительную роль в процессе складывания государственности сыграли торговые и культурные связи с Индией и Китаем, появление индийских и китайских колонистов, а также проникновение буддизма и индуизма. Центром возникавших прибрежных государств обычно был портовый город в устье реки, со временем распространявший свою власть на близлежащую долину. Как правило, большинство таких малых государств рано или поздно попадали в фактическую или номинальную вассальную зависимость от более сильных и крупных соседей. В 3-6 вв. малаккские государства находились в зависимости от империи Фунань, в 8 в. попали в зависимость от суматранской империи Шривиджайя. В конце 13 в. северные княжества (наиболее значительное — Тамбралинга) оказались под властью тайских государств. Во второй половине 14 в. княжества на юге полуострова признавали власть индонезийской империи Маджапахит.

В 15 — начале 16 вв. полуостров Малакка, архипелаг Риау и восточная часть острова Суматра были объединены под властью Малаккского султаната. С его образованием началось быстрое распространение ислама. В это же время на севере острова Калимантан возвысился и султанат Бруней, подчинивший почти всю северную часть острова Калимантан (территория современных штатов Сабах и Саравак).

В 1511 г. территория Малаккского султаната была захвачена португальскими колонизаторами. Вскоре на территории западной части Малайзии — в Малайе образовалось несколько султанатов, самым значительным из которых был Джохор (на юге полуострова Малакка). В течение 16-18 вв. Джохор пытался объединить под своей властью всю территорию Малайи и избавиться от зависимости от европейцев (португальцев, а затем голландцев). Соперником Джохора выступал также и индонезийский султанат Аче (север острова Суматра). В 1641 г. голландцы, заручившись союзом с Джохором, отбили у португальцев Малакку, а во второй половине 17 в. власть Джохора распространялась уже на значительную часть Малайи и восточное побережье Суматры.

В конце 17 — начале 18 вв. с Джохором, испытывавшим серьезные внутренние и внешние затруднения, схлестнулись голландцы, стремившиеся установить свой контроль над добычей олова и торговыми путями через Малаккский пролив. В ходе двух войн с Джохором голландцы сломили сопротивление и навязали Джохору неравноправный договор. В конце 18 в. Джохор распался на ряд феодальных владений, и территория Западной Малайзии была окончательно раздроблена. Попытки испанцев в конце 16 в. закрепиться в Восточной Малайзии, являющейся тогда территорией султаната Бруней, окончились неудачей.

С конца 18 в. решающее влияние на историю малайских государств начала оказывать английская колониальная экспансия. Англичане захватили остров Пинанг (1786 г.), провинцию Уэлсли (1800 г.), остров Сингапур (1819 г.) и по Лондонскому англо-голландскому договору 1824 г. добились признания Малайи своей сферой влияния. В 1826 г. владения Великобритании в Малайе были объединены в «президентство» с Индией — Стрейтс-Сетлментс. В 1867 г. из Стрейтс-Сетлментс была образована отдельная колония, включавшая такие важнейшие морские порты, как Сингапур, Малакка и Пинанг, а также провинцию Уэлсли.

В 1870-1880-х годах Великобритания захватила малайские княжества Перак, Селангор, Негри-Сембилан и Паханг, являвшиеся наиболее экономически развитыми районами полуострова Малакка, которые в 1896 г. объединились в федерацию. В 1909 г. король Сиама был вынужден передать Великобритании находившиеся под сиамским господством на севере полуострова Малакка султанаты Кедах, Келантан, Тренгану и Перлис, которые не были включены в федерацию. Последним из малайских княжеств в 1914 г. был подчинен Джохор, тоже оставшийся вне федерации. Из всех этих малайских владений Великобритании была образована колония Британская Малайя.

В 1841 г. английский авантюрист Джеймс Брук получил от султана Брунея в управление Саравак на острове Калимантан, где основал династию так называемых «белых раджей». В 1881-1882 гг. образовалась Британская компания Северного Борнео, к концу 19 в. распространившая свою власть на весь Сабах. А в 1888 г. над территорией современной Восточной Малайзии (штатов Саравак и Сабах) был установлен английский протекторат. Малайя, Сабах и Саравак стали превращаться в аграрно-сырьевой придаток Великобритании и в сферу приложения английского капитала. Малайя стала страной монокультуры каучука и поставщиком олова, Сабах и Саравак давали лес, нефть, каучук, перец. Появились плантации экспортных культур, крупные оловянные рудники, банки, торгового дома, страховые и транспортные компании.

С декабря 1941 по 1945 г. Малайзия была оккупирована Японией, установившей военно-колониальный режим. Японское вторжение вызвало к жизни мощную волну народного сопротивления, получившего название «Движение трех звезд», от трех основных национальностей Малайи. Попытка англичан после капитуляции Японии в 1945 г. восстановить здесь свои колониальные порядки закончилась фиаско, переродив антияпонское сопротивление в антибританское.

Согласно конституционным реформам 1946 и 1948 гг. Сингапур был отделен от Малайи, ставшей отдельной колонией — Малайским Союзом, а с 1948 г. — Малайской Федерацией. В 1946 г. княжества Сабах и Саравак формально перешли в ведение министерства колоний Великобритании.
В июне 1948 г. английские власти, стремясь подавить национально-освободительное движение в Малайской Федерации, ввели там чрезвычайное положение. В феврале 1949 г. была создана Освободительная армия народов Малайи. Союз трех партий (Объединенной малайской национальной организации, Китайской ассоциации Малайи и Индийского конгресса Малайи) одержал победу на выборах 1955 года в Законодательный совет Малайской Федерации, выступив за независимость Федерации в рамках британского Содружества. Продолжительная конфронтация с Англией закончилась обретением Малайской Федерацией независимости (провозглашена 31 августа 1957 г.), а 9 июня 1963 г. в Лондоне было подписано новое соглашение между Великобританией, Малайской Федерацией, Сингапуром, Сабахом и Сараваком об образовании «Федерации Малайзия в рамках Британского Содружества». Независимая Федерация Малайзия была провозглашена 16 сентября 1963. Включение в Федерацию Малайзия северного Калимантана (Сабах и Саравак) привело к осложнению отношений с Индонезией и Филиппинами. Обострение отношений федерального правительства Малайзии с Сингапуром, вызванное экономическими, политическими и национальными проблемами, привело к выходу Сингапура из состава Федерации 9 августа 1965 г.