1957-ben a Maláj Föderáció (Federation of Malaya) függetlenné vált, de Szingapúr brit koronagyarmat maradt, mivel a brit kormány és a maláj politikai elit is tartott a sziget erős baloldali, részben kommunista befolyás alatt álló mozgalmaitól. A Maláj-félsziget és Szingapúr gazdasága azonban szorosan összefonódott: a sziget kikötője, kereskedelme és feldolgozóipara a félszigeti nyersanyagokra támaszkodott, míg a maláj kormány a szingapúri vámokból és kikötői bevételekből remélt többletforrást. Az észak-borneói területek, Sabah és Sarawak, valamint Brunei csatlakozásának ötlete a demográfiai egyensúly miatt is felmerült: a maláj és kínai népesség aránya a Maláj-félszigeten közel kiegyenlített volt, és a maláj politikai elit attól tartott, hogy a szingapúri, többségében kínai lakosság bevonása felborítaná a maláj politikai dominanciát. A borneói őslakos és maláj közösségek bevonásával a maláj politikai erők remélték, hogy ellensúlyozzák a kínai demográfiai nyomást.
A tervet Tunku Abdul Rahman malajziai miniszterelnök 1961 májusában egy beszédében hozta nyilvánosságra, „Malajzia” néven. A javaslat szerint a Maláj Föderáció, Szingapúr, Észak-Borneó (a későbbi Sabah), Sarawak és Brunei egy új föderációvá egyesült volna. A tervet a brit kormány támogatta, mert a dekolonizáció ekkorra már a térségben lezárult, és London tartott az indonéziai befolyás növekedésétől, valamint a kommunista mozgalmak térnyerésétől. A hidegháború logikája szerint a maláj és brit döntéshozók a föderációt a stabilitás eszközének tekintették. A terv ugyanakkor vitatott volt a leendő tagállamok lakosságának egyes csoportjai körében: Szingapúrban a baloldali Barisan Sosialis (Szocialista Front) ellenezte a csatlakozást, mert az a „maláj uralom” alatti másodrendű státuszt jelentette volna; Sabahban és Sarawakban a bennszülött közösségek egy része attól tartott, hogy a félszigeti elitek gyarmatiasítják őket; Brunei szultánja, Omar Ali Saifuddien szintén nem csatlakozott, mert nem akarta megosztani az olajbevételeket a központi kormánnyal.
A brit kormány 1961-ben létrehozta a Cobbold-bizottságot Lord Cobbold vezetésével, hogy felmérje Észak-Borneó és Sarawak lakosságának véleményét a föderációról. A bizottság 1962 júniusában kiadott jelentése szerint a lakosság többsége támogatta a csatlakozást, de a támogatottság mértékét és a módszertant a történészek vita tárgyává tették. A jelentés ugyanakkor hangsúlyozta, hogy Sabah és Sarawak speciális jogait, bennszülött közösségeinek védelmét és a Maláj-félszigettől való elkülönülését garantálni kell. A tárgyalások során ezeket a feltételeket beépítették a készülő alkotmányos dokumentumokba.
Szingapúrban 1962. szeptember 1-jén népszavazást tartottak a Malajziához való csatlakozásról. A népszavazás eredményeként a szavazók elutasították a teljes függetlenséget, és a csatlakozást választották, de a szavazólap három lehetőséget kínált, és a baloldali ellenzék a szavazás bojkottjára szólított fel. A szavazási részvétel így alacsony volt, ami a legitimitás kérdését vetette fel. A szavazás eredményeként Szingapúr csatlakozott a föderációhoz, de a baloldali mozgalmak továbbra is erősek maradtak, ami a későbbi konfliktusok egyik gyökere lett.
A tárgyalások 1963 júliusában zárultak a Malajziai Megállapodás (Malaysia Agreement 1963) aláírásával Londonban. Az aláírók: a brit kormány, a Maláj Föderáció, Szingapúr, Észak-Borneó és Sarawak. Brunei nem írta alá, és kimaradt a föderációból. A megállapodás rögzítette a szövetségi alkotmány módosításait, a tagállami autonómiákat, a bevándorlási jogköröket, az állampolgársági szabályokat, a pénzügyi megállapodásokat és a bennszülött jogok védelmét. A maláj nyelvet hivatalos nyelvként rögzítették, de Szingapúrban az angol, Sabahban és Sarawakban az angol és a bennszülött nyelvek is használatban maradtak.
A Fülöp-szigetek 1962-ben bejelentette igényét Észak-Borneóra, a Sulu szultánság egykori területeire hivatkozva, ami diplomáciai vitát robbantott ki. A brit és maláj kormány elutasította a követelést, de a Fülöp-szigetek továbbra is fenntartotta igényét, és ez hozzájárult a föderáció létrejötte körüli nemzetközi feszültséghez. Indonézia, amely Sukarno elnök vezetésével a föderációt a brit imperializmus folytatásának tekintette, szintén ellenezte a tervet, és 1963-ban konfrontációt hirdetett.
A Malajziai Föderációt 1963. szeptember 16-án kiáltották ki Kuala Lumpurban. A dátumot azonban diplomáciai nyomás miatt elhalasztották az eredeti, augusztus 31-i időpontról, mert a Fülöp-szigetek és Indonézia azt követelte, hogy az ENSZ vizsgálóbizottsága ellenőrizze Sabah és Sarawak lakosságának véleményét. Az ENSZ vizsgálóbizottság jelentése a többség támogatását állapította meg, de a Fülöp-szigetek és Indonézia a jelentést elutasította, és továbbra sem ismerte el a föderációt.
Indonézia 1963-ban meghirdette a Konfrontasi (Konfrontáció) politikáját, amely fegyveres beszivárgást, szabotázsakciókat és diplomáciai támadásokat jelentett Malajzia ellen. A konfrontáció a hidegháború egyik regionális konfliktusává vált, amelyben a britek, az ausztrálok és az új-zélandiak katonailag támogatták Malajziát, míg Indonézia a Szovjetunióval és Kínával ápolt kapcsolatokat. A konfrontáció 1966-ban, a Sukarno-rezsim bukását követően ért véget, de ez már a malajziai belpolitika feszültségeitől függetlenül is megterhelte a fiatal föderációt.
Az 1963-as föderáció létrejöttével Malajzia föderációvá vált, amelynek tagállamai: a Maláj-félsziget államai, Szingapúr, Sabah és Sarawak. Az államforma alkotmányos monarchia volt, a maláj szultánok választották a Yang di-Pertuan Agong (a legfőbb uralkodó) tisztségét, és a parlament kétkamarás volt: a Szenátus (Dewan Negara) és a Képviselőház (Dewan Rakyat). A központi kormány Kuala Lumpurban székelt, és a védelem, a külügy, a belbiztonság és a pénzügy a szövetségi hatáskörbe tartozott.
Szingapúr 1963-as csatlakozásának feltételei különlegesek voltak: a sziget megtarthatta saját kormányát, oktatási rendszerét, pénzügyi autonómiáját és bevándorlási ellenőrzését, de a védelem és a külügy a központi kormányhoz tartozott. A szingapúri választási rendszerben a People’s Action Party (PAP) dominált, amelynek vezetője, Lee Kuan Yew miniszterelnök lett. A PAP már a csatlakozás előtt ambiciózus politikai programot hirdetett, amely a „Malajziai Malajzia” (Malaysian Malaysia) eszméjén alapult: minden állampolgár egyenlő jogaira, a faji alapú megkülönböztetés elutasítására és a gazdasági modernizációra helyezte a hangsúlyt. Ez a program szemben állt a Maláj Föderációban érvényesülő bumiputera-politikával, amely a maláj és őslakos lakosság különleges jogait védte.
A szövetségi szinten a Maláj Föderációt az UMNO (United Malays National Organisation), a Malajziai Kínai Szövetség (MCA) és a Malajziai Indiai Kongresszus (MIC) koalíciója, a Szövetség (Alliance) kormányozta. Az UMNO a maláj etnikum érdekeit képviselte, és a maláj politikai dominancia fenntartását tekintette elsődleges célnak. Az MCA a kínai közösség gazdasági és kulturális érdekeit képviselte, de a maláj politikai hegemóniában alárendelt szerepet játszott. Az MIC az indiai közösség érdekeit képviselte, de befolyása kisebb volt. A szövetségi kormány és a szingapúri PAP közötti viszony hamar feszültté vált, mert a PAP a szövetségi választásokon is elindult, és a kínai szavazók mobilizálásával próbálta megváltoztatni a maláj politikai hegemóniát.
Az 1964-es szövetségi választásokon a PAP jelöltjei indultak, de az UMNO radikális szárnya ezt a maláj uralom elleni támadásnak tekintette. A szingapúri kampány során a faji feszültség fokozódott, és 1964 júliusában és szeptemberében zavargások törtek ki Szingapúrban. A zavargásokban maláj és kínai közösségek tagjai csaptak össze, és több tucat ember meghalt. A zavargások okai között szerepeltek a faji politikai mobilizáció, a gazdasági egyenlőtlenségek és a provokatív beszédek. A maláj kormány a PAP-t vádolta a feszültség szításával, míg a PAP az UMNO radikálisait tette felelőssé. A történészek ma úgy látják, hogy a zavargások hátterében a két politikai erő versengése és a faji alapú politikai mobilizáció állt, de a pontos felelősség vitatott.
A zavargások után a PAP 1965-ben meghirdette a Malajziai Malajzia kampányát, amely a föderáció egészére kiterjedő politikai reformot javasolt: a rassz alapú pártok helyett a multietnikus pártok támogatását, a maláj különjogok fokozatos csökkentését és az esélyegyenlőség növelését. Az UMNO vezetése ezt a maláj alkotmányos jogok elleni támadásként értékelte, és a szövetségi kormány válaszul nyomást gyakorolt a szingapúri kormányra. A konfliktus a gazdasági és pénzügyi vitákban is megnyilvánult: Szingapúr nem volt hajlandó a közös piac feltételeit elfogadni, és a maláj kormány vámokkal és kereskedelmi korlátozásokkal sújtotta a szigetet.
A feszültség 1965 nyarán tetőzött, amikor az UMNO radikálisai Szingapúr kizárását követelték. Tunku Abdul Rahman és Lee Kuan Yew tárgyalásokat folytattak, és 1965. augusztus 9-én a malajziai parlament hozzájárult Szingapúr kiválásához. A szingapúri kilépés dokumentált tény, de a hivatalos narratíva szerint Szingapúr „békés úton” vált függetlenné, míg a kritikus történészek szerint a kilépés de facto kizárás volt, amelyet a maláj politikai elit kezdeményezett, hogy megőrizze a maláj dominanciát. A kilépés mögött a politikai és faji feszültségek mellett gazdasági érdekellentétek is álltak: Szingapúr a föderációban nem kapta meg a várt vámmentes hozzáférést a félszigeti piachoz, és a közös valuta is vitatott volt.
Szingapúr 1965. augusztus 9-én kikiáltotta függetlenségét, és Szingapúri Köztársaság néven önálló állammá vált. A szingapúri kilépés a Malajziai Föderáció alaptörvényének módosítását igényelte, mert a föderáció tagjai közül Szingapúr kivált. A kilépés után Malajzia föderáció maradt, de Sabah, Sarawak és a Maláj-félsziget államai alkották. A maláj–kínai–indiai viszony a föderáción belül is feszült maradt, és az 1969-es választási zavargásokig tovább romlott, de ez már a következő alfejezet tárgya.
A Malajziai Megállapodás értelmében Sabah és Sarawak jelentős autonómiát kapott: bevándorlási ellenőrzést, a bennszülött jogok védelmét, az oktatás és a vallási intézmények feletti részleges rendelkezést. A félszigeti államokkal szemben itt a maláj etnikum nem alkotott többséget, hanem a bennszülött csoportok mellett a kínai közösség is jelentős részarányt képviselt. Az alkotmányos berendezkedés a maláj nyelvet hivatalos nyelvként, az iszlámot a föderáció vallásaként ismerte el, de a vallásszabadságot garantálta. A maláj különjogokat az alkotmány ideiglenesnek nevezte, de a gyakorlatban a maláj politikai elit folyamatosan védte.
A szövetségi állam politikai rendszerét a konszociációs modellhez szokták hasonlítani, amelyben a nagy etnikai csoportok elitjei alkudoznak a hatalom megosztásáról. Az UMNO dominanciája azonban egyértelmű volt: a miniszterelnök mindig az UMNO vezetője lett, a maláj nyelv és a maláj kultúra állami támogatást kapott, és a kínai és indiai pártok szerepe a koalíciós rendszerben alárendelt maradt. Az 1963-as föderáció létrejötte után a kínai közösség egy része a PAP elveit támogatta, míg más része az MCA-n keresztül próbált érdekérvényesítést szerezni. Az indiai közösség politikai befolyása kisebb volt, és a gazdasági szerepük is korlátozottabb maradt.
A szövetségi állam strukturális feszültségei tehát már 1963-ban jelen voltak: a maláj politikai dominancia és a bumiputera-különjogok, a kínai gazdasági befolyás, a szingapúri multietnikus modell és a borneói autonómiák közötti ellentétek meghatározták a fiatal föderáció politikai dinamikáját. A szingapúri kilépés után a maláj politikai elit megerősítette a maláj nemzetállami jelleget, de a kínai és indiai kisebbségek állampolgári jogai és gazdasági szerepe továbbra is vitatott maradt. Az 1963-as megalakulás és az 1965-ös kilépés így nem csupán alkotmányos esemény, hanem a malajziai nemzetépítés mély törésvonalainak kifejeződése volt.
Az 1963-as Malajziai Megállapodás szövege, a Cobbold-jelentés, a szingapúri népszavazási jegyzőkönyvek és a korabeli maláj, brit és szingapúri parlamenti viták elsődleges forrásokként hozzáférhetők. A statisztikai adatok – például a népszavazási részvétel, a zavargások áldozatainak száma – esetében fontos megjegyezni, hogy a korabeli hatósági jelentések pontatlanok lehetnek, és a későbbi szakirodalmi becslések eltérhetnek. A legfőbb bizonytalansági pontok a következők: Sabah és Sarawak lakosságának tényleges véleményét a Cobbold-bizottság és az ENSZ-bizottság módszertana nem tudta egyértelműen rögzíteni; a szingapúri népszavazás a szavazólap kialakítása és a baloldali bojkott miatt vitatott legitimitású; a szingapúri kilépés okainak és felelőseinek megítélése eltér a malajziai és a szingapúri hivatalos narratívákban. A maláj–kínai–indiai viszonyok alakulását a korabeli sajtó és a politikai beszédek tükrözik, de a közösségek hétköznapi tapasztalatairól kevesebb forrás áll rendelkezésre. A konfrontáció és a brit katonai szerepvállalás dokumentumai a brit levéltárakban kutathatók, de a részletes elemzés további levéltári munkát igényel. A források egy részéhez az interneten keresztül is hozzáférhető, de a hivatkozott szakirodalmat – például a Malajzia megalakulásáról szóló monográfiákat – itt nem volt mód közvetlenül ellenőrizni, ezért a pontos hivatkozási adatok a végső szerkesztés során pótolandók.