tidlige europæiske indtrængen og nye sultanater
malaccas berømmelse som krydset mellem asiatisk handel var nået Europa i begyndelsen af det 16.århundrede. Portugiserne, der i et århundrede havde søgt en søvej til Østasien, ankom endelig til Malacca i 1509 og indviede en ny æra med europæisk aktivitet i Sydøstasien. Selvom meget af Sydøstasien, inklusive det nordlige Borneo, oplevede lidt vestlig indflydelse før det 19.århundrede, Malaya var en af de første regioner, der blev forstyrret. I 1511 erobrede en portugisisk flåde under ledelse af Afonso Malacca.
fordi få købmænd i Malacca valgte at udholde erobrernes høje skatter og intolerance over for Islam, forsvandt byen i sidste ende under portugisisk kontrol. Det sultanat af Aceh (Acheh) i det nordlige Sumatra sprang efterfølgende ind i det politiske vakuum skabt af Malaccas tilbagegang, og i det 16.og tidlige 17. århundrede var Acehnese dybt involveret i halvøforhold, der kæmpede mod forskellige sultanater og til tider kontrollerede nogle eller de fleste af dem. Faktisk var den underbemandede portugisiske myndighed i Malacca næppe i stand til at afvise gentagne angreb fra sultanatet Aceh. I mellemtiden opstod hollænderne, efter at have etableret det hollandske østindiske selskab i 1602, som den dominerende europæiske magt i Sydøstasien. I 1641 greb hollænderne Malacca, og selvom de forsøgte at genoplive sin handel, genvandt byen aldrig sin tidligere herlighed.
gennem Malacca ‘ s opkomst og fald opstod nye sultanater andre steder i den malaysiske verden. De var normalt beliggende ved mundingen af en større flod og forsøgte at kontrollere handel til og fra det indre, som ofte blev befolket af seminomadiske folk som f.eks aboriginal Orang Asli (“oprindelige folk”) af Malaya og de forskellige oprindelige folk i Borneo. Yngre sultanater-såsom Riau—Johor og Kedah, begge på halvøen, og Brunei, på Borneos nordlige kyst-overtog nogle af Malacca ‘ s handelsfunktioner og blomstrede i flere århundreder. Islam nåede andre områder af det nordlige Borneo i det 15. og 16. århundrede; mange kystfolk konverterede, men de fleste af indbyggerne i det indre fortsatte med at praktisere lokale religioner langt ind i det 20.århundrede. Malaysisk politisk kontrol spredte sig, hvor Brunei—sultanerne hævdede meget af det, der i dag er Saravak og Sabah-skønt deres faktiske magt sjældent nåede meget ud over kystområdet. Bruneis forsøg på at kontrollere det indre mislykkedes ofte, især efter den aggressive Iban (Sea Dayak) folk begyndte deres vandringer ind i nutidens Saravak fra det vestlige Borneo (16.til 18. århundrede). Siameserne kom til at kontrollere nogle af de nordlige Malaysiske sultanater, og den sydligste del af det nuværende Thailand har stadig en overvejende Malaysisk muslimsk befolkning. De malaysiske sultanater omfattede mange, ofte feudende Høvdinger. Derfor udbrudte krige inden for og mellem sultanaterne fra tid til anden. Fra europæernes perspektiv var sultanatsystemet—med dets hierarkiske, men svingende indflydelsessfærer over mobile befolkninger-politisk ustabilt.
i løbet af det 17.århundrede vandrede mange Minangkabau-folk fra det vestlige Sumatra ind i det sydvestlige Malaya og bragte med sig et matrilinealt sociokulturelt system, hvorved ejendom og autoritet faldt ned gennem den kvindelige side. De valgte deres høvdinge blandt kvalificerede aristokratiske kandidater, en model, der er blevet indarbejdet i det moderne Malaysias valg af en konge. Senere dannede Minangkabau en sammenslutning af ni små stater (Negeri Sembilan). Den politiske pluralisme i Malaya i det 18.århundrede lettede også storstilet penetration af halvøen af Buginesere fra sydvestlige Celebes, en stor ø sydøst for Borneo, der nu er en del af Indonesien. Med et velfortjent ry som maritime handlende etablerede Buginesiske indvandrere Sultanatet Selangor på Malayas vestkyst i midten af 1700-tallet. mod sydøst fik de fremtrædende plads i Sultanatet Johor, som på spidsen af halvøen var en velstående handelsvirksomhed, der tiltrak asiatiske og europæiske købmænd. På trods af kontinuerlig bevægelse af folk fra øhavet ind i området forblev Malaya og det nordlige Borneo tyndt befolket i det tidlige 19.århundrede. Mange nutidige malajer er efterkommere af indvandrere fra andre steder i arkipelagisk Sydøstasien, der ankom efter 1800. Faktisk demonstrerede indvandrere fra Java, Celebes og Sumatra en tendens til at assimilere sig til det eksisterende Malaysiske samfund over tid, en proces, der støt accelererede med stigningen i malaysisk nationalisme og folkelig uddannelse i 1930 ‘ erne. Nogle af traditionerne bragt af Minangkabau, Javanesere og andre indvandrere praktiseres stadig i distrikter, hvor de bosatte sig, hvilket bidrager til de mange regionale variationer af malaysisk kultur og sprog.