马六甲王国的兴起
信诃补罗王国被满者伯夷消灭后，该地的厄运并未结束。北方的暹罗趁机把势力伸向该地，在这里设立了一名酋长来管理这一地区，这一地区自然受到暹罗保护。
大约在淡马锡王国兴起的同一时期，公元8世纪（相当于中国唐朝时期），在今天印度尼西亚苏门答腊岛巨港（Palembang）地区兴起了室利佛逝王国（又译三佛齐王国）。这个王国在公元9世纪至13世纪与邻近的印度尼西亚爪哇群岛中部的夏连特拉王国（Syailendra）和东部的满者伯夷王国等持续展开混战并逐渐衰败。曾经强大的室利佛逝势力范围不断缩小，最终收缩到都城巨港附近。至室利佛逝王国的末代王子拜里米苏拉（1344—1414年，马来语名为Parameswara，可能来自梵文，意为“至高无上的君主”，中文又译作拜里迷苏剌）登基不久，满者伯夷再度进犯室利佛逝。此时的室利佛逝已然处于内忧外患的危机时刻，满者伯夷王国处心积虑要吞并室利佛逝。为与满者伯夷结好，拜里米苏拉加强了与爪哇群岛的往来，甚至娶了满者伯夷的友邻杜马班国国王的女儿为妻，向岳父称臣纳贡，请求他替自己向满者伯夷说好话，以求自保。然而，巨港、杜马班、满者伯夷三方政治联姻并没能为室利佛逝带来安全。没过多久，满者伯夷还是向室利佛逝发起了最后的总攻，因双方实力悬殊，室利佛逝的巨港和占碑很快被攻破，室利佛逝王国就这样灭亡了。根据《马来纪年》记载，亡国后的室利佛逝王族拜里米苏拉带着妻子和臣民起先流亡到与今新加坡隔海相望的廖内群岛暂时栖居，随后乘船渡海逃亡到马来半岛最南端，即今天的新加坡。
拜里米苏拉来到此地后，起先受到当地酋长的热烈欢迎。不久，拜里米苏拉刺杀了当地酋长，占领了此地并自立为王。关于这件事引发的后果有两个传说版本。
第一个版本说，拜里米苏拉的行为立即引起了当地保护国暹罗方面的强烈不满。当时该酋长有一位女婿正任马来半岛中部彭亨的国王，为给岳父报仇，遂依靠暹罗王国的支持，挥兵南下讨伐拜里米苏拉。暹罗方面调派驻扎彭亨的军队前来讨伐拜里米苏拉，拜里米苏拉最终败逃。暹罗收复此地后，并未加以积极经营，此地仍是一个破败的小渔村。
另一个版本则称，拜里米苏拉在此地统治了5年，发现并不是什么好地方，土地贫瘠、国库空虚（可见当初此地沦落之深），于是开始考虑迁都。
无论是在第一个版本还是第二个版本的传说，拜里米苏拉最终离开此地，逃往马来半岛的麻坡（Muar）。当拜里米苏拉逃到麻坡的时候，本想在麻坡安营扎寨，但却受到壁虎的困扰。原来，麻坡一带有许多壁虎，一到晚上，就密密麻麻地在营地附近出现，爬满地面，骚扰士兵们休息。到了第二天，人们就一齐捕杀壁虎，把它们投入河中。可到了晚上，无数的壁虎又开始在营地里活动，很难根除。由于河里积累的壁虎尸体越来越多且发出恶臭，因此人们就把麻坡称为“臭壁虎之城”（Kota Biawak Busuk），这个别称至今仍流传在马来西亚的麻坡地区。
马来民众中流传的拜里米苏拉像
拜里米苏拉的逃亡队伍不堪壁虎的滋扰，不得不继续北迁。随后，他们找到了一处新营地，开始建造城堡。可奇怪的是，每当他们在白天建好城堡，到了深夜总会无缘无故坍塌下来，看来这个地方也很难定居，因此人们把此地称为“Kota Buruk”（毁灭之城），今天在马来西亚仍可看到毁灭之城的遗址。
拜里米苏拉的队伍为了生存只能继续向马来半岛北部迁移。经过长途跋涉，他们最终来到马六甲河口附近，在这里建立了城池（在今马来西亚的马六甲）。拜里米苏拉决心发愤图强，重振国威。
毁灭之城遗址
今天的马六甲河
传说拜里米苏拉在此定居后，一天，他和随从到马六甲河附近狩猎，到了正午，就和随从在一棵枝繁叶茂的大树下乘凉休息。忽然，他看到不远处一条猎狗正猛力追赶一只鼠鹿，鼠鹿一路狂奔到河边，陷入绝境，竟突然停了下来转向猎狗迎了上去。猎狗奋力向前扑击，鼠鹿又一个转身把猎狗踢入河中。好一个漂亮的绝地反击！这是弱者的反击！看到这一幕的拜里米苏拉不禁大喜，联想到家国的遭遇，顿感浑身倍添动力，认为这是一块福地，连弱小的鼠鹿都能把猎狗打败，自己也一定能像鼠鹿那样击败其他强国。他认定这里必能保证其干出一番伟业，便坚定了在此建国的决心。拜里米苏拉随后又指着自己身边的一棵大树问随从叫什么名字。随从回答叫马六甲树（Pokok Melaka），拜里米苏拉遂决定将新建立的国家称为马六甲。从此，马六甲成为马来西亚和新加坡历史上极为重要的一页。
勇于绝地反击的神奇动物鼠鹿
事实果然如此。马六甲城池周围有充足的水源和广阔的平原，靠山观海，地势险要，易守难攻。这里扼守马六甲海峡的最窄处，是各国商船必经的地方，加上地处热带，有着充沛的降雨、充足的阳光、肥沃的土壤、可供开垦的土地，往往能获得不错的收成，因此很快就成为著名的商港和政治经济中心，成为马六甲王国的根基。
在随后的近一个世纪里，马六甲王国不断发展壮大，国土一度扩展至今天的泰国南部、马来西亚整个西马地区、新加坡全境和印度尼西亚苏门答腊岛西南地区，而王城就位于今天马来西亚的马六甲市。马六甲王国的政治、经济、文化、艺术等各方面，可以说对现代马来西亚和新加坡的思想和文化影响极为深远。
1424年拜里米苏拉逝世，葬于今马来西亚波德申港（Port Dickson）附近的丹绒端（Tanjung Tuan），另一说就葬于禁山（Bukit Larangan，今新加坡福康宁山），其长子依斯甘达沙继任苏丹。
建国初期的马六甲十分弱小，当时并未正式称国，也没有严格的政府组织和国家制度，北面经常受到暹罗武装力量的侵扰，南面又有满者伯夷王国的威胁。拜里米苏拉自知国力尚弱，只好向暹罗求和，每年进贡黄金40两，自称藩属。此后，真正使马六甲走向强大的，还是来自中国明朝的帮助。
在马六甲王国建国后没多久，1403年（永乐元年），明成祖从侄儿建文帝手中夺得皇权，随后派遣京官尹庆率舰队访问南洋诸国。尹庆在马六甲见到了拜里米苏拉，认为马六甲地理位置极佳，并赠予拜里米苏拉许多礼物。
当时，拜里米苏拉经历了一系列挫折，又面临暹罗的侵扰，正是穷困潦倒之际，得此礼遇自然备受感动；又从尹庆口中听到明朝的富庶强大，顿生仰慕之情，便向尹庆诉苦，控诉暹罗的侵扰，表示自己极不愿向暹罗上贡，愿成为明朝的藩属以获庇护。尹庆建议其派出使者，同返明朝朝见皇帝，请求明朝的庇护，使暹罗不敢进攻。于是，马六甲的使者随尹庆到明朝拜见了明成祖。明成祖十分高兴，一方面予以厚待，一方面正式颁赠诏书和印玺，册封拜里米苏拉为“满剌加国”国王，并赏赐黄伞等物，从此黄伞也成为马六甲王室乃至今天马来西亚王室的标志，最常在登基或宣誓就职时使用。自此，明朝和马六甲王国开启了一段融洽和亲密的关系。
1405年郑和首下西洋就抵达马六甲并拜见了拜里米苏拉。拜里米苏拉为表感谢，于1407年派使团再次访问明朝，两国关系进一步发展。随后郑和三次到达马六甲，给当地带去大批明朝物产和先进文化。明朝与世界各国的文化、经济上的频繁往来、马六甲优越的地理位置也使马六甲快速成为东南亚的交通和商贸中心。马六甲逐步繁荣了起来。拜里米苏拉对明朝的文化充满仰慕之情和好奇心，在郑和的邀请下，1411年，他带着王妃、王子及臣子等500人随郑和访问明朝。拜里米苏拉在此期间虚心学习文化，参照明朝礼仪、风俗习惯和政治思想，回国后制定了马六甲王朝各种制度。1424年，拜里米苏拉病逝，儿子穆罕默德·伊斯干达沙（Mohammad Iskandar Shah）继位。暹罗人见拜里米苏拉去世，曾几次入侵马六甲，但都因明朝的调解和庇护而失败。拜里米苏拉以接受明朝册封的方式从暹罗的虎口下保存和发展了马六甲王国。
纪念中国与马六甲友好交往历史的邮票，右下角分别为中国古货币与马六甲货币
此后，马六甲王国在历任国王的带领下逐渐兴盛起来。当时，王国采取了联姻和武力并用的方式，让附近的岛屿自愿接受马六甲王国的统治，马六甲王国的领土不断扩大。周边还有许多国家对马六甲王国进贡。
到国王穆扎法尔·沙统治时期（1445—1459年），马六甲王国对内宣布伊斯兰教为国教，国王始称苏丹，改称“苏丹穆萨法沙”（此后的马六甲王国准确地应称为马六甲苏丹国，但为叙述方便，本书仍沿用王国的称呼）。王国起用著名政治家敦·佩拉克任“槃陀诃罗”（即首相）。对内，他缓和马来贵族和泰米尔贵族之间的矛盾，加强王国内部的团结；对外，他两次击败暹罗入侵并遣使暹罗主动修好，结束了两国间的长期不和。王国的势力范围包括马来半岛南部（含今新加坡），并逐渐扩展至马来半岛北部的克拉地峡与南面的苏门答腊岛的一部分，控制了马六甲海峡的航运。当时中国发明的指南针已被马六甲王国用于航海，中国铸造钱币的技术也流传到马六甲王国。
国王曼苏尔·沙统治时期（1459—1477年），马六甲王国进入鼎盛时期。他把国家大权交给槃陀诃罗敦·佩拉克掌管。从1459年起，王国凭借强大的国力，在马来半岛进行统一战争，先后征服彭亨、柔佛、雪兰莪、霹雳、丁加奴、吉兰丹等地，逐渐形成今天新加坡—马来西亚的领域轮廓。具体来说，此时的马六甲王国涵盖马来西亚半岛、泰国南部一部分、苏门答腊岛的大部分；并控制马六甲海峡的海上交通和贸易，实行政权单一管制。当时的马六甲海峡是亚洲黄金水道，马六甲港口是国际贸易中心，各国商人聚集在这里进行贸易。领土的迅速扩大、经济的空前繁荣，使马六甲王国成为当时东南亚最强大的封建国家之一。
此时的马六甲王国，苏丹是最高统治者，苏丹以下有3位大臣分别掌管政务：一为“槃陀诃罗”，掌管国家政务和外交；二为“天猛公”，掌管国家军务和司法；三为“奔呼庐槃陀诃罗”，掌管征税、纳贡等事宜。
马六甲王国已成为东西方最大的贸易集散地之一。印度人、阿拉伯人和波斯人用商船运来棉花、染料、香料和药品，中国商船带来丝绸、锦缎、布匹、瓷器。在最繁盛的时期，马六甲王国拥有4万常住人口，有马来人、华人、阿拉伯人，还有来自印度、锡兰、波斯、暹罗、高棉、占碑、爪哇等地的商人。在当时，此地可以听到各种不同的语言，感受到各种不同的文化，远超淡马锡、信诃补罗时期。
马六甲王国经济的繁荣，使它逐步取代巨港和爪哇成为东南亚新的贸易转运中心，并在当时形成了一个以马六甲王国为中心的“区域商贸圈”。该商贸圈附有南北两条弧线：北方弧线形成较早，包括从占城（今越南南部）、高棉及暹罗沿海直到马六甲王国；南方弧线形成稍迟，从菲律宾群岛经婆罗洲、西里伯斯、马鲁古群岛、巽他海峡、爪哇、苏门答腊直到马六甲王国。这一区域性商贸圈的出现，不仅使沟通东西方的中介贸易空前繁荣，也使整个东南亚地区内部联系空前活跃。马六甲王国在促进东南亚地区内外发展上功不可没。
马六甲王国迅速兴盛的原因，值得深思。
首先，中国明朝在其发展崛起过程中起到至关重要的作用。马六甲王国位于东南半岛的最南端，立国之初只是一个偏僻的小渔村，且经常受到北方强大的暹罗的侵扰，甚至被迫向暹罗屈服和进贡，这在一定程度上束缚了马六甲王国早期的发展壮大。在郑和下西洋前夕，明朝派遣尹庆到访马六甲王国，马六甲王国利用这个机会请求明朝保护，以此摆脱了暹罗的政治压制。中国明朝官员马欢所著、成书于景泰二年（1451年）的《瀛涯胜览》“满剌加”条记载，“此处旧不称国，因海有五屿之名，遂名曰五屿，无国王，止有头目掌管。此地属暹罗所辖，岁输金四十两，否则差人征伐。永乐七年己丑，上命正使太监郑和等，统赍诏敕，赐头目双台银印冠带袍服，建碑封城，遂名满剌加国。是后暹罗莫敢侵扰。其头目蒙恩为王，挈妻子赴京朝谢，贡进方物。朝廷又赐与海船，回国守土”。由此可见，明朝对马六甲国王的册封加强了马六甲王国在国际社会立足的稳定性，对马六甲王国摆脱暹罗的侵扰起了一定作用，客观上有利于马六甲王国经济的发展。
其次，马六甲王国的兴盛离不开其自身的奋斗。马六甲王国立国之初，仅是一个偏僻的渔村、一片蛮荒之地，甚至有海盗巢穴。当地的气候朝热暮寒，缺少农业资源。其国东南是大海，西北是老岸连山，皆沙卤之地……田瘦谷薄，人们从耕种中的所得非常有限。在室利佛逝王国崩溃后，满者伯夷王国内部政治出现混乱而无力统辖马六甲海峡地区，拜里米苏拉及其后代正好抓住这一有利时机，在马六甲海峡建立起了强盛的马六甲王国，统治地域涵盖并超过了今新加坡和马来西亚。当时的爪哇（位于今天印度尼西亚地区）是东南亚各海岛的农业中心，是马六甲王国粮食供应的主要来源之一，爪哇的商船频繁往来于爪哇与马六甲王国之间，运去大米和胡椒，换回印度棉布和以丝绸、瓷器为主的中国商品。这种经济联系减少了马六甲王国与爪哇的敌对关系，加强了它们之间的经济交流。除此之外，原先与马六甲王国敌对的暹罗也逐步与马六甲王国进行贸易往来。暹罗主要向马六甲王国出口大米，进口香料、胡椒、织锦等。同时今缅甸的勃固王朝也向马六甲王国出口粮食等产品，而位于婆罗洲东海岸的渤泥国（今文莱）也积极与马六甲王国发展贸易合作。这就使马六甲王国逐渐打开了同周边邻国的关系，站稳了脚跟并兴盛起来。
马六甲王国苏丹宫殿遗址
此外，统治者政策的得当也是马六甲王国繁荣的重要原因之一。拜里米苏拉招徕各方商人到马六甲王国经商。香料、稻米、胡椒贸易促使了马六甲王国的进一步繁荣。
随着马六甲王国的崛起发展，它与明朝的关系也得到了不断加强。15世纪末16世纪初，王国先后遣使明朝达30余次，其中仅国王本人亲自率领使团访问就达5次。明朝政府自1403年派官员尹庆访问马六甲起直到1481年，曾14次遣使访问马六甲。中国许多先进的生产技术，如犁、耙等农具传到马六甲后，改变了马来人农业生产的落后状况，中国的指南针也被马来人用在航海上，促进了当地航海事业的发展。当时马来人运到中国的玳瑁、沉香、乳香等药品，也成为中国医师常用的良药。中国文学名著《红楼梦》中提到的眼镜最早也是在15世纪由西方国家经马六甲王国传入中国的。直到今天，仍流传着许多有关马六甲王国与明朝友好关系的历史佳话。
拜里米苏拉及其开创的马六甲王国历史对于马来半岛（包括新加坡）来说极其重要，《马来纪年》全书都以马六甲王国的历史为主线来撰写马来地区的历史，并尊崇马六甲王室的祖先为亚历山大大帝的后裔，认为马六甲王室有着来自西方的高贵血统和不凡身世。