新马合并与短暂的联邦岁月
李光耀是伟大的理想主义者，同时也很现实。他领导的人民行动党在探索由自治迈向独立的道路上，最早提出的解决方案是将新生的“新加坡自治邦”与同为英国殖民地出身并早一步于1957年取得自治的“马来亚联合邦”合并，共同组建一个强大的、由马来人和华人联合而成的“马来西亚联邦”，然后共同宣布该联邦独立，各族群共享联邦的繁荣。
该政治设想并不是凭空产生的。回顾新加坡辉煌的古代史就能知道，将新加坡与整个马来亚半岛、马来亚地区合并在一起的政治设想，是建立在马六甲王国与柔佛王国悠久的历史文化传统之上的，也建立在华人与马来人长期共同生活、共同发展的现实基础上，更是新加坡这个人口仅有数百万的城市国家维持基本生存不得不做出的现实选择。在李光耀看来，新加坡既缺乏资源，又无战略后方，在狭小的领土独立建国实属勉强，因此最好的选择是以整个马来亚半岛、马来亚地区为依托，与马来亚联合邦实现合并。
在这一设想上，李光耀与同期“马来亚联合邦”的领导人不谋而合。1961年5月27日，“马来亚联合邦”的首相东姑拉赫曼（Tunku Abdul Rahman，后被称为“马来西亚国父”）提议“马来亚联合邦”与新加坡、沙捞越、北婆罗洲及文莱王国合组一个强大的联邦国家，实现更紧密的经济及政治合作。他的提议反映了马华两族人民联合自强、建设美好家园的共同呼声，因而得到了人民的广泛支持。
对于东姑拉赫曼的提议，人民行动党表示赞成，但左翼人士担心合并将对其不利，林清祥等13人宣布脱离人民行动党，另组“社会主义阵线”，反对新马合并。对此，李光耀决定于1962年9月1日在新加坡举行全民公投，选票上印有三个选项：
我支持合并，新加坡获得劳工、教育和其他议定事项的自主权，同时新加坡公民自动成为马来西亚公民；
我支持全部及无条件的合并，新加坡应以一州的地位，根据马来亚联合邦的宪法文件，与其他十一州在平等基础上进行合并；
我支持新加坡加入马来西亚，条件应不逊于婆罗洲地区所获得者。
由于选票上并没有设定反对合并的选项，因此林清祥等人领导的社会主义阵线呼吁民众投空白票。最终公投结果显示，71%的民众支持第一选项，只有26%的人响应社会主义阵线号召投了空白票。随后，东姑拉赫曼与李光耀共同签署了合并条款，决定共同组建一个负责国防、外交与国家安全事务的中央政府。为清除合并道路上的障碍，1963年2月，李光耀政府在英国与马来西亚的支持下，发起了“冷藏行动”，将多位社会主义阵线人士逮捕下狱。
1963年9月16日，“马来西亚联邦”正式成立，其领土包括马来亚联合邦、新加坡自治邦、沙捞越和北婆罗洲（即今马来西亚沙巴州）等，位于加里曼丹岛的文莱王国因发生叛乱而拒绝合并。按照合并条款，1963年9月16日这天，新加坡成为马来西亚联邦下辖的一个州，同时保留了教育和劳工自治权。这就是历史上著名的“新马合并”。
然而，新马合并组建强大的联邦一事引发邻国印度尼西亚和菲律宾的不满。为此，新成立的马来西亚联邦还一度与印度尼西亚出现外交危机。其实，当马来亚联合邦1957年8月正式独立时，印度尼西亚与马来亚的关系并不糟糕，印度尼西亚不仅立即予以承认，而且在1959年还与其签署了友好条约。然而，随着1963年马来西亚联邦的宣告成立，印度尼西亚和马来西亚联邦的关系发生急剧变化。印度尼西亚时任总统苏加诺认为本国拥有北婆罗洲主权，同时认为马来西亚联邦的成立是“英帝国主义的表现”。苏加诺这一认识与当时的国际背景密不可分。1956年，英国主张在远东地区部署核武器，1958年决定在新加坡“秘密兴建核武库”，1962年送原子弹到新加坡，次年进行投掷训练。印度尼西亚总统苏加诺奉行亲左翼政策，因而认为英国在新加坡部署核武器有针对印度尼西亚之意，且新马合并有共同应对遏制左翼力量之考虑，于是对马来西亚联邦的成立持怀疑态度，认为这是对印度尼西亚的包围，是英国殖民主义者的阴谋。1963年1月20日，苏加诺发起“粉碎马来西亚运动”，反对沙巴和沙捞越并入马来西亚联邦并支持文莱民众发起的反对加入马来西亚联邦的运动。1963年9月马来西亚联邦成立后，印度尼西亚旋即宣布与其断交。此后，双方处于敌对状态并一度发生武装冲突。这种敌对状态一直持续到1966年8月苏加诺政权被苏哈托政变推翻才结束。苏哈托在印度尼西亚执政后，1966年8月与马来西亚联邦签署关系正常化协议，1967年复交。
李光耀与东姑拉赫曼
菲律宾对“强大”的马来西亚联邦的出现也表示反对，并就沙巴的主权提出要求。他们认为，沙巴历史上曾是该国苏禄苏丹管辖的地区，因此应属菲领土。不过，时任菲总统费迪南德·马科斯并没有采取苏加诺那样激烈的反对政策，随后承认了马来西亚联邦对沙巴的主权。
如前所述，1963年9月16日，“马来西亚联邦”正式成立，其领土包括马来亚联合邦、新加坡自治邦、沙捞越和北婆罗洲（今马来西亚沙巴州）等。其中，“马来亚联合邦”主要由马来联邦、马来属邦、一部分前海峡殖民地辖区和新获得土地四部分构成，其与英国殖民马来半岛及新加坡历史密不可分。
在“马来亚联合邦”建立之前有“马来联邦”。马来联邦是1896年7月5日由彭亨、雪兰莪、霹雳与森美兰四邦合组而来，它们受英国保护，实际上属于英国控制范围。马来联邦的实权集中在以英国总驻扎官（1911年后改为首席部长）为首的联邦政府手中，总驻扎官从属于马来联邦高级专员（由海峡殖民地总督兼任），高级专员负责与英国殖民部联系。马来联邦还设统治者会议、驻扎官会议、联邦参议会（1927年改为联邦议会）。统治者会议于1897年举行。联邦参议会为立法机构，于1909年成立，由高级专员主持。非官方议员由高级专员提名，经英王批准后任命。联邦参议会并没有族群代表性。到1927年，在8名非官方议员中，有5名仍是欧洲人，有2名是华人，1名是马来酋长。“马来联邦”下辖诸邦均有一个相对独立的政府，由苏丹、英国驻扎官、顾问及邦参议会组成，但诸邦向联邦政府交出了大部分实权，包括税收权、财政权，地方苏丹的权力大为削弱。1877年9月11日，霹雳邦成立参议会，这是除海峡殖民地外，马来各邦中第一个立法机构。邦参议会主席由苏丹担任，成员包括英国派驻的驻扎官、主要的马来族酋长和两三名华人巨商，其主要工作是在立法方面，所有土邦立法均由其通过。1927年参议会改组为联邦议会后，马来统治者退出，但议会通过的法案均须经4个统治者签署才能生效。
所谓“马来属邦”，是对马来半岛未参加马来联邦的各邦之统称，包括吉兰丹、吉打、丁加奴、玻璃市和柔佛5邦。其中前4个邦，即吉兰丹、吉打、丁加奴、玻璃市是根据1909年《英暹条约》由暹罗改属英国管辖。马来属邦下辖各邦在行政上各自为政，比马来联邦下辖各邦保留有较多实权，各邦政治体制也保留了较多的马来传统，但也受到时代影响，出现了一些新形式。柔佛邦则与前四者不同，它一直是历史上柔佛王国的统治中心，名义上由苏丹统治，但实际上也受到英国殖民者辖制。1895年，柔佛邦颁布了由英国律师起草的成文宪法，决定成立部长会议作为苏丹的咨询机构，成员须为穆斯林，同时决定设立邦参议会作为立法机构，成员仅限柔佛臣民，但不限信仰，后又增设行政会议，作为行政补充。但无论如何，马来属邦均须由英国顾问“协助”管理政务，实际上仍类似于驻扎官制度，名为顾问，实可左右苏丹决策。
一部分前海峡殖民地辖区，主要包括槟榔城、马六甲两地。早在19世纪，英国曾将所占领管辖下的几个不相连的属地——新加坡、槟榔屿、马六甲等合称为“海峡殖民地”，起初由位于印度加尔各答的东印度公司和印度总督管理，1867年移交给伦敦的殖民地事务大臣，其中槟榔屿与新加坡曾先后成为海峡殖民地的行政中心。第二次世界大战结束后，英国于1946年1月颁布白皮书决定组建“马来亚联合邦”，将槟榔屿、马六甲两地纳入其中，但将新加坡剥离出来，实行新马分治、区别对待，新加坡仍属英国的“直辖殖民地”。
所谓“新获得土地”，主要包括19世纪后半叶英国从荷属婆罗洲（即今加里曼丹岛）北部沿海一带的沙捞越、沙巴和纳闽地区。其中，沙捞越地区原由文莱王国苏丹统治，沙巴地区原本由西属菲律宾控制的苏禄苏丹统治，纳闽则是原属于文莱王国的一处南海小岛。1841年，英国探险家詹姆士·布鲁克（James Brooke）从文莱王国苏丹奥玛·阿里（Omar Ali）手中租借了婆罗洲北部沿海的古晋市（今马来西亚沙捞越州首府），此后不断从文莱苏丹手中取得领土，英国商人也开始在沙捞越殖民并向沙巴扩展。1881年，英国北婆罗洲公司控制沙捞越、沙巴地区并受新加坡总督辖制。1888年，整个文莱王国沦为英国的保护国，文莱承认沙捞越地区属英。至于沙巴，原本统治该地方的苏禄苏丹（效忠于西属菲律宾）一直不承认英国对沙巴领土的所有权，但事实是该地被英国人控制并由后来的马来亚联合邦、马来西亚联邦继承。纳闽于1846年被文莱苏丹割让给英国并被改名为“维多利亚岛”，1848年成为英国皇家殖民地，并于1890年1月1日被英国合并为英属北婆罗洲的一部分。1906年10月30日，纳闽被英国合并为海峡殖民地的一部分。1942年太平洋战争爆发，马来半岛（含新加坡）、北婆罗洲被日军占领，纳闽被改名为“前田岛”。第二次世界大战后纳闽于1946年加入新成立的“马来亚联合邦”。