马来亚独立后，这个区域还有其它英国领地的前途悬而未决，日本投降后，布鲁克家族和英国北婆罗洲公司分别放弃了对砂拉越和沙巴的控制，这些地区成为英国皇家殖民地。相较于马来亚，这些地区的经济发展落后得多，当地的政治领袖过于软弱，而未寻求独立，而且这些地区与马来亚的文化区别也相当大，以华人占多数的新加坡于1955年获得自主权，1959年当时年轻的社会主义运动领导人李光耀成为新加坡首席部长，盛产石油的文莱苏丹国依然是英国附属，1959年与1962年之间，英国政府召集了多次复杂的谈判，在这些当地领导人与马来亚政府之间进行协商。

1961年东古阿卜杜勒·拉赫曼赞成建立“马来西亚”的构想，马来西亚将包括曾是英国海外领地的文莱、马来亚、沙巴、砂拉越和新加坡，其背后的理由则是容许中央政府控制并打击共产党（尤其是在新加坡）的活动，此外马来亚也惧怕新加坡一旦独立，将会成为华人沙文主义者的基地，威胁马来人的统治权，为了平衡种族比例，在文莱、沙巴与砂拉越纳入这个新国家之后，它们的马来人及土著人口，将可抵消新加坡的华人多数。

虽然新加坡首席部长李光耀支持这个建议，但他在新加坡社会主义阵线的党内反对者反对这个计划，认为这是英国打算继续控制这个区域的计谋，砂拉越大多数政党也反对这个计划，沙巴没有政党，但是当地社团代表也表示反对，文莱苏丹支持这个计划，但是文莱人民党反对，在1961年的英联邦首席部长联合会议(Commonwealth Prime Ministers Conference)，东古阿卜杜勒·拉赫曼向他的反对者进一步阐述这个计划，10月，英国政府批准这个计划，条件是必须取得参与这项合并计划的地区同意，葛波(Lord Cobbold)率领葛波委员会前往婆罗洲研究当地居民意见，认为沙巴和砂拉越同意合并，但在文莱则有许多人反对，在新加坡的公民投票中70%的人赞成合并，条件是新加坡政府获得实质的自主权，文莱苏丹退出这项参组马来西亚的计划，这是由于来自多数人民的反对、关于石油利润分配比例的争执，以及关于合并后苏丹的地位等等因素，此外，文莱的人民党发动武装革命，虽然立刻遭到敉平，但被视为这个新国家潜在的不稳定因素。

英国政府讨论葛波委员会的报告后，又设立Landsdowne委员会来起草马来西亚宪法的草稿，最后出炉的新宪法草案与1957年的马来亚宪法基本上相同，只做了少部分修改，例如，原先对于马来人特殊地位的认定，扩及到砂拉越与沙巴的所有土著，新加坡、砂拉越与沙巴这三个新加入的国，也被赋予某些自主权，这是原先的九个马来亚州署所没有的，因为新加坡、砂拉越与沙巴是以国的地位与马来亚联邦共同组成马来西亚联邦。

1963年7月的谈判结束后，决定马来西亚联邦将于1963年8月31日正式成立，这天恰好是马来亚独立以及英国赋予新加坡和沙巴自治权的纪念日，然而，菲律宾和印度尼西亚强烈反对这个事态发展，印度尼西亚称马来西亚为新殖民主义的代表，而菲律宾则强调沙巴是她的领土，印尼总统苏加诺在强大的印度尼西亚共产党的支持下提出反对，而且砂拉越人民联合党发动了多次抗争行动，延迟了马来西亚的成立，基于这些因素，联合国组成一个八人代表团造访砂拉越与沙巴，确认他们参组马来西亚的意愿。

马来西亚正式于1963年9月16日成立，由马来亚、沙巴、砂拉越与新加坡共同组成，当年的马来西亚人口约一千万人。