在1025年与1026年,刚迦王国遭到古淡米尔国朱罗王朝皇帝Rajendra Chola I 攻打,使得三佛齐的第一个都城哥打格兰基因而荒废。朱罗王朝的入侵减损了三佛齐的威望,三佛齐曾将其影响力施展到吉打、北大年,远至单马令。
2世纪的一首淡米尔文诗Pattinapalai,描写来自吉打的货物堆积在朱罗王朝首都的景象。7世纪的一出梵文戏剧Kaumudhimahotsva,将吉打称为卡达哈州(Kataha-nagari)。Agnipurana也提及卡达哈的领地以一座高峰为边界,学者相信这就是吉打的日莱峰。来自Katasaritasagaram的故事描写卡达哈的高贵生活。不久之后,信奉佛教的单马令王国控制了吉打。在11世纪,单马令国王Chandrabhanu利用吉打做为攻打斯里兰卡的基地,这个事件记录在泰米尔纳德邦Nagapattinum的石碑,以及斯里兰卡的编年史《大史》.
拜里米苏拉向北前进,以建立一个新的根据地。在麻坡,拜里米苏拉考虑将他的新王国建立在Biawak Busuk或Kota Buruk。在发现麻坡的地点并不合适之后,他继续往北走。据信他在沿路曾造访Sening Ujong (双溪乌荣Sungai Ujong的旧名,即现在的芙蓉市),随后到达Bertam河(马六甲河的旧名)的河口,建立了马六甲苏丹王朝。历经时间演变,这个地方发展成今天的马六甲。依据《马来纪年》记载,拜里米苏拉在一株“满剌加树”(Malacca tree,又名余甘子)下,看见一条猎狗将一头鼷鹿(mouse deer)逼到绝境,小鼷鹿为了自卫,将狗踢进河里。他将这个景象视为好兆头,决定在此建立一个名为马六甲(Melaka,Malacca)的王国。他建立并改善贸易设施。
在马六甲建国之时,中国明朝皇帝明成祖派出舰队以扩展贸易。舰队首领郑和造访马六甲,并带着拜里米苏拉返回中国,承认他是马六甲合法统治者的地位,明成祖封他为满剌加国王。为了交换定期的进贡,中国皇帝提供马六甲保护,以抵抗暹罗的不断威胁。在这个时代前后,在马来半岛定居的华人和印度人成为今天峇峇娘惹和Chetti社群的祖先。根据一种理论,当拜里米苏拉娶了Pasai公主之后,成为一个穆斯林,他采用当时流行的波斯衔头"Shah"(国王),自称依斯干达国王(Iskandar Shah)。 据中国史书记载,在1414年,这位马六甲第一位统治者的儿子晋见明成祖,告以父亲去世的消息。拜里米苏拉的儿子随即受到承认,为马六甲第二任统治者,名为Raja Sri Rama Vikrama, Raja of Parameswara of Temasek and Melaka,他的穆斯林人民称他Sultan Sri Iskandar Zulkarnain Shah 或Sultan Megat Iskandar Shah。他从1414到1424年统治马六甲。 透过印度穆斯林以及少部份来自中国的回人所影响,伊斯兰教在15世纪变得越来越普遍。
马六甲很快就占据了过去三佛齐所统治的地区,与中国建立了独立的外交关系,并控制中国通向印度的海上贸易道路。由于蒙古的扩张,这时从中国通向西方的陆路被阻,这条海上贸易通道就变得越来越重要。马六甲建国后数年内,正式采行伊斯兰教,其国王称号由拉者(Raja)改为苏丹(Sultan)。马六甲苏丹王朝的政治势力帮助伊斯兰教传遍马来群岛,马六甲当时身为马来亚半岛最繁盛的王国,使这个信仰得以传播到邻国。到了16世纪开头,伊斯兰教成为马来人的主要宗教,其势力到达现在的菲律宾,只有巴厘岛依然是一个孤立的印度教岛屿。
争夺霸权:
奥斯曼帝国阻断了欧洲与亚洲之间的陆路贸易路线,而且与印度及东南亚的贸易受到阿拉伯商人所垄断,迫使欧洲国家寻找一条通向印度的海路。1498年葡萄牙国王若昂二世派出瓦斯科·达·伽马(Vasco da Gama),发现了绕过好望角通向印度的海路。1511年阿方索·迪·阿不奎(Afonso de Albuquerque)带领远征舰队来到马来亚,经过一个月的围攻,他占领了马六甲。马六甲成为葡萄牙在东方活动的核心据点。
1607年,亚齐苏丹国兴起,成为马来群岛最强盛富裕的国家。在伊斯干达.穆达(Iskandar Muda)统治下,这个苏丹国控制的范围延伸到苏门达腊与马来半岛的大部分地区。他征服马来半岛的锡矿产地彭亨。他所向披靡的舰队在1629年攻打马六甲的战役中瓦解,依据葡萄牙史书记载,当时葡萄牙与柔佛的联军设法摧毁他的所有船舰,杀掉19,000名战士。然而,亚齐的军力并未被摧毁,因为在同一年亚齐征服了吉打并把许多吉打人民迁到亚齐。这位苏丹的养子 Iskandar Thani先前是彭亨的王子,后来成为他的继承人。在Iskandar Thani统治期间,亚齐专注于巩固内部及宗教上的统一。
在17世纪初,荷兰建立了荷兰东印度公司(英文:Dutch East India Company,荷兰文:Vereenigde Oost-Indische Compagnie,简称VOC),一开始建立在摩鹿加群岛的贸易,他们很快就占据了爪哇岛上较弱的苏丹国,1619年建立巴达维亚为他们的首府。他们从巴达维亚扩展势力到马来群岛,与柔佛结盟来对付他们的主要敌人:马六甲的葡萄牙人和强大的亚齐苏丹国。1641年,在数次尝试后,荷兰与柔佛的联军终于攻占马六甲,终结了葡萄牙的统治,葡萄牙仅剩下葡属帝汶。在荷兰的支持下,柔佛在马来亚的各个苏丹国之间,获得一个松散的霸权地位,只有霹雳例外,它能够周旋于柔佛和暹罗之间,并保持其独立。
走向马来西亚:
华人对马共的反对,呈现于1949年筹组的马华公会(Malayan Chinese Association,MCA),它成为调节华人政治意见的渠道。其领导人陈祯禄愿意与巫统合作,建立一个所有公民平等的独立的马来亚,但同时在马来人敏感的议题上做出充分让步,来平息马来民族主义者的恐惧。1951年吉打王子东古阿卜杜勒·拉赫曼继奥恩·加法尔之后,担任巫统领导人,陈祯禄与东古阿卜杜勒·拉赫曼密切合作。由于1949年英国人宣布无论马来人愿意与否,马来亚将在数年内获得独立,两位领导人必须下定决心来提出在两个社群均可接受的一个协议,成为一个稳定的独立国家的基础。这个巫统-华人公会联盟(后来印度人国大党也加入了这个联盟)在1952年和1955年的大选中,在马来人和华人地区均获胜。