То, что Малаккский полуостров – место, мягко говоря, выгодное, понимали не только европейцы. С завидным постоянством он становился частью самых разных империй древнего мира. Скажем, государство Фунань одним из первых на этой земле контролировало северную часть полуострова, а начиная с VII века он принадлежал великой Суматранской империи Шривиджайя уже целиком. Это время было эпохой расцвета индо-буддийского периода этого региона. По прошествии веков Шривиджайя пала под ударами нового Яванского царства Маджапахит. Однако один из суматранских принцев, Парамесвара, сумел основать здесь в 1403 году город Малакку, на долгие годы ставший стратегическим центром всего региона. Именно этот момент и можно считать точкой отсчета того, что в конечном итоге превратилось в сегодняшнюю Малайзию.
В 1405 году, когда стало ясно, что Малакка постепенно становится средоточием как торговых, так и политических устремлений, сюда прибыл посол китайской династии Мин адмирал Чен Хо – с предложением, от которого нельзя было отказаться. Поднебесная предлагала новому малайскому государству свое покровительство и защиту от вполне реальных притязаний со стороны соседнего Сиама. В результате принц Парамесвара был объявлен королем Малакки и всех прилегающих территорий, а на берегах пролива появились первые китайцы. В Малакке запылали жертвенные костры новых переселенцев, привезших с собой свои обычаи и верования. Процесс космополитизации города-государства получил новый дополнительный толчок.
Тем временем для множества купцов со всей Азии Малакка становилась буквально вторым домом. Именно тогда вместе с арабскими торговцами в эти края попал ислам. Потребовалось совсем немного времени, чтобы он стал здесь главенствующим. Уже третий правитель Малакки, махараджа Моххамед Шах, перешел в ислам, а его сын Муджаффар Шах, принявший титул султана, сделал его государственной религией.
Конец XV столетия явился золотой эпохой Малаккского султаната. О его богатстве ходили легенды. Он превращался в признанного лидера всей мусульманской Азии. И, наконец, весть о нем достигла берегов Европы. Конечно, о существовании этой земли в Старом Свете знали и раньше – она была обозначена еще на первых картах Птолемея. Однако если до начала XVI века особого интереса к Малаккскому полуострову европейцы не проявляли, то стремительное возвышение Малаккского султаната явно меняло дело.