Точная дата основания города Малакки неизвестна. Историки считают, что укрепленный город на месте рыбацкой деревни возле устья реки Бертам был основан около 1400 года от рождества Христова малайским правителем Парамешварой из древнего рода царей Шривиджаи. Тесные связи с мусульманами Суматры привели к обращению в ислам сначала правителей Малакки, а потом и их окружения, и на протяжении двух столетий Малакка оставалась крупнейшим центром ислама на Малайском полуострове.

Во второй половине XIII века малайское царство Шривиджая со столицей в Палембанге (на юге острова Суматра) начало терять позиции в борьбе со своими постоянными соперниками с острова Ява. Помимо очевидного материального интереса, выражавшегося в контроле над ресурсами и морским путем, соединявшем Китай и Индию, враждебность соседей по архипелагу подогревалась и религиозными различиями. Жители Шривиджаи исповедовали буддизм и считали себя подданными китайских императоров династии Сун (хотя и не были их данниками в полном смысле этого слова), в то время как на Яве доминировал смешанный индуистско-буддистский культ.

В середине XIII века центральная власть в Шривиджаи была сильно ослаблена, и именно в этот период на севере Суматры возник султанат Самудра Пасай. Это было одно из первых (если не первое) мусульманское государство на Малайских островах. Арабские и индийские мусульмане издавна торговали с Шривиджаей и Китаем, и на востоке острова Ява есть мусульманские могилы, датируемые второй половиной XI в. Есть мнение, что в середине IX в. на Суматре существовал султанат Пеуреулак (Перлак), но оно не подтверждается надёжными источниками. А вот в 1267 г. правитель небольшого города на севере Суматры раджа Мерах Силу принял ислам и провозгласил себя султаном с титулом аль-Малик ас-Салих. В 1292 г. гостем султана был венецианский путешественник Марко Поло, пробывший на Суматре несколько месяцев.

Благодаря своему расположению в северо-восточной оконечности архипелага, Самудра Пасай стал центром притяжения мусульманских торговцев и проповедников. Однако влияние ислама на местных жителей было ещё слишком мало. Люди поклонялась первому, что попадалось им на глаза, а некоторые племена даже ели человеческое мясо. Тем не менее султанат просуществовал более двух столетий, вплоть до португальского вторжения на острова, и сыграл важную роль в распространении ислама на Малайском полуострове.

В 1286—92 гг. правитель яванского царства Сингхасари — Кертанегара — совершил Памалайский поход на Суматру и захватил большую часть малайских земель, включая крупнейшие города Палембанг и Джамби. Успехи Кертанегары, однако, привлекли внимание хана Хубилая из монгольской династии Юань, который к тому времени разгромил армию южной династии Сун и объединил Китай. Военная верхушка монголов требовала расширения сферы влияния Юань на соседние государства, которые в прежние времена платили дань китайским императорам. Прибывшие на Яву послы потребовали от Кертанегары признать себя вассалом Великого хана. Тот оскорбил послов и отказался платить дань, и уже в 1293 г. монгольский флот из тысячи кораблей приблизился к берегам Явы.

Однако ситуация в Сингхасари внезапно изменилась. Кертанегара был убит своим вассалом адипати (княжеский титул) Джаякатвангом, который и захватил власть. Когда же монгольская армия высадилась на остров, зять убитого царя Раден Виджая вступил в переговоры с монголами и при их поддержке сверг узурпатора. Как только яванские войска перешли в его подчинение, он неожиданно напал на монголов и потребовал от них покинуть остров. Муссонные ветры вот-вот должны были перемениться, и, случись такое, монголам пришлось бы ждать шесть месяцев, чтобы благополучно вернуться домой. Понимая, что ситуация сложилась не в их пользу, они отступили. Ражен Виджая провозгласил себя царём и принял имя Кертараджаса Джаявардхана, а его столицей стал новый город Маджапахит на востоке Явы.

По мере расширения государства его ядром стали острова Ява и Бали, находившиеся под прямым управлением Маджапахита, а правители Суматры, Сулавеси, Мадуры, Сумбавы, Борнео, Паханга и других областей признали себя его вассалами. Фактически с конца XIII в. Шривиджая утратила самостоятельность, а Маджапахит превратился в одно из самых могущественных государств в истории Малайского архипелага.

Тем не менее Шривиджая не прекращала попыток освободиться от зависимости. Когда после свержения монголов к власти в Китае пришёл Чжу Юаньчжан, основатель династии Мин, правители Паханга и Палембанга неоднократно отправляли послов к императору в надежде восстановить прежние связи. В 1377 г. китайский император, наконец, согласился признать Палембанг своим вассалом и отправил туда посольство. Когда об этом узнали в Маджапахите, посольство было задержано и доставлено на Яву, где китайские послы были убиты.

Узнав о реальном положении дел на островах, император разгневался и обвинил Шривиджаю в предательстве. Но даже оставшись без союзников, Шривиджая не прекратила борьбу. Очередное восстание в Палембанге в 1391 г. было жестоко подавлено, после чего юг Суматры был разорён.

С этого момента Шривиджае с политическим центром на Суматре наследует небольшой остров Темасек (на самом юге Малайского полуострова). Государство это называется Сингапур, а его царь Парамешвара ведёт своё происхождение от правителей Шривиджаи.

Авторы «Малайской родословной» утверждают, что Сингапур был основан приблизительно в 1299 г. потомком царей Палембанга, известным как Санг Нила Утама. Однако достоверность этого документа весьма сомнительная — он был создан лишь в XVI веке после того, как малайские города были захвачены португальцами, и для обоснования исторического права на власть султанов Малакки и Джохора.

Санг Нила Утама в «Малайской родословной» предстаёт сыном Санг Сапурбы, легендарного царя малайцев. Он спускается с гор и женится на дочери Деманг Лебар Дауна, правителя Палембанга. Его сын Санг Нила Утама некоторое время правит на небольшом острове Бинтан, а затем поселяется на Темасеке и называет своё царство Сингапур, что на санскрите означает «город льва». Три поколения его потомков благополучно правят на острове, а четвёртым оказывается Солаи Парам (в малайских анналах он именуется Искандер-шах, а в португальских — Парамешвара). Историчность этой личности не вызывает сомнений, но подробности его жизни окутаны тайной.

Согласно португальским хронистам, Парамешвара был изгнан яванцами из Палембанга, когда попытался поднять там восстание. Спустя некоторое время он прибыл на Темасек и через восемь дней убил тамошнего правителя Санг Аджи (Сангесинга). Следующие пять лет он правил на Темасеке, но был вынужден бежать, когда остров атаковали войска Маджапахита или тайского царства Аютия. Авторы «Малайской родословной» утверждают, что Искандер-шах бежал из Сингапура в 1398 г. после того, как огромная армия Маджапахита завоевала город спустя месяц после начала осады.

Обе версии можно объявить в предвзятости, но обе они согласны в том, что правитель Сингапура спасается бегством и вместе со своим окружением отправляется на север. Поначалу Парамешвара останавливается в Муаре, на побережье Малаккского пролива, но местность оказывается неподходящей для расселения, и беглецы двигаются дальше, пока не достигают рыбацкого поселения в устье реки Бертам (современная река Малакка). Произошло это около 1400 года.

Согласно «Малайским родословным», Искандер-шах отдыхал под амалакой (индийским крыжовником), когда увидел, как небольшой оленёк загнал в реку его охотничью собаку. Он счёл это добрым знаком и решил поселиться в этом месте. Считается, что Малакка получила своё название именно от этого дерева, а на гербе города и в наше время можно увидеть двух оленьков.

Место было благоприятным для выращивания бананов, сахарного тростника, ямса и других культур, а бухта надёжно защищала корабли от сильных приливов и отливов. Эти обстоятельства быстро сделали Мелакку привлекательной для торговцев, тем более что в Палембанге к тому времени обосновались китайские пираты, грабившие проходившие мимо корабли.

Когда слава нового города докатилась до Пекина, император Юнлэ отправил в Малакку посольство во главе с Инь Цином. Визит, состоявшийся в 1405 г., ознаменовал начало тесных сношений между двумя государствами. Парамешвара был рад заручиться поддержкой Китая против своих соседей, и в 1411 г. он вместе со своей семьей и многочисленной свитой отправился в Пекин, чтобы собственноручно выплатить дань императору. Юнлэ принял его с почестями и в знак признания его законным правителем наградил печатью и символами власти. Вдобавок Парамешвара вернулся в Малакку вместе с огромным императорским флотом, во главе которого стоял евнух-мусульманин Чжэн Хэ, что обеспечило городу защиту от китайских пиратов и Маджапахита.

Из записей китайского путешественника Ма Хуана, также исповедовавшего ислам, который посетил Малакку вместе с Чжэн Хэ, мы узнаём, что город был обнесён частоколом с несколькими башнями и четырьмя воротами. Река разделяла Малакку на две почти равные части: в южной части находилась защищенная цитадель, резиденция правителя и дома его приближенных, а в северной части проживали иностранные торговцы.

Согласно китайским хроникам, в 1414 г. сын первого правителя Малакки прибыл ко двору императора, чтобы сообщить о смерти своего отца и выплатить дань. После смерти Парамешвары власть в Малакке перешла к его сыну Мегат Искандер-шаху. Это обстоятельство подтверждается как китайскими, так и португальскими источниками. Поэтому современные историки считают неверной малайскую легенду о том, что основателем Малакки был Искандер-шах. Скорее, им был его отец Парамешвара, а Искандер-шах правил городом после его смерти вплоть до 1424 г.

Малайские источники также утверждают, что в 1409 г. основатель Малакки принял ислам и женился на дочери султана Самудра Пасай. Доверять этому сообщению можно не более, чем трактату Suma Oriental португальского дипломата Томе Пиреса (XVI век), в котором утверждается, что Мегат Искандер-шах принял ислам, когда ему было 72 года (за восемь лет до его смерти).

Очевидно, что уже первые правители Малакки не противились деятельности мусульманских проповедников. В тот период ислам быстро распространялся в прибрежных городах Суматры, а Самудра Пасай и Пеуреулак были самостоятельными исламскими монархиями. А уже при султане Мухаммад-шахе (1424–1444), сыне Мегат Искандер-шаха, если верить «Малайским родословным», в ислам начали обращаться вельможи из его окружения.

Таким образом, наследовав языческому царству Шривиджая, Малаккский султанат к середине XV века превратился в сильное мусульманское государство, претендовавшее на гегемонию в регионе. Это вызывало обеспокоенность и в ослабленном Маджапахите, и в Аютии (Аюттхая), которая успешно объединяла тайские земли. Решающая схватка между Малаккой и Аютией была лишь вопросом времени.