Sa panahon pagkatapos ng Ikalawang Digmaang Pandaigdig , ang mga adhikain para sa isang nagkakaisa at nagkakaisang bansa ay humantong sa panukalang bumuo ng Malaysia.Ang ideya, na unang iminungkahi ng pinuno ng Singapore na si Lee Kuan Yew kay Tunku Abdul Rahman, Punong Ministro ng Malaya, ay naglalayong pagsamahin ang Malaya, Singapore , North Borneo, Sarawak, at Brunei.^[83] Ang konsepto ng pederasyong ito ay sinuportahan ng paniwala na pipigilin nito ang mga aktibidad ng komunista sa Singapore at mapanatili ang balanseng etniko, na pumipigil sa Singapore na mangibabaw ang mayorya ng Tsino.^[84] Gayunpaman, ang panukala ay nahaharap sa pagtutol: Sinalungat ito ng Socialist Front ng Singapore, gayundin ang mga kinatawan ng komunidad mula sa North Borneo at mga paksyon sa pulitika sa Brunei.Upang masuri ang posibilidad ng pagsasanib na ito, itinatag ang Cobbold Commission upang maunawaan ang mga damdamin ng mga naninirahan sa Sarawak at North Borneo.Habang ang mga natuklasan ng komisyon ay pumabor sa isang pagsasanib para sa North Borneo at Sarawak, ang mga Bruneian ay higit na tumutol, na humahantong sa tuluyang pagbubukod ng Brunei.Parehong iminungkahi ng North Borneo at Sarawak ang mga tuntunin para sa kanilang pagsasama, na humahantong sa 20-point at 18-point na kasunduan ayon sa pagkakabanggit.Sa kabila ng mga kasunduang ito, nanatili ang mga alalahanin na ang mga karapatan ng Sarawak at North Borneo ay nalalabo sa paglipas ng panahon.Ang pagsasama ng Singapore ay nakumpirma na ang 70% ng populasyon nito ay sumusuporta sa pagsasanib sa pamamagitan ng isang reperendum, ngunit sa kondisyon ng makabuluhang awtonomiya ng estado.^[85]Sa kabila ng mga panloob na negosasyong ito, nagpatuloy ang mga panlabas na hamon.Ang Indonesia at Pilipinas ay tumutol sa pagbuo ng Malaysia, kung saan kinikilala ito ng Indonesia bilang "neokolonyalismo" at inaangkin ng Pilipinas ang North Borneo.Ang mga pagtutol na ito, kasama ng panloob na pagsalungat, ay ipinagpaliban ang opisyal na pagbuo ng Malaysia.^[86] Kasunod ng mga pagsusuri ng isang pangkat ng UN, ang Malaysia ay pormal na itinatag noong 16 Setyembre 1963, na binubuo ng Malaya, North Borneo, Sarawak, at Singapore, na nagmarka ng isang mahalagang kabanata sa kasaysayan ng Timog-silangang Asya.