Berdasarkan [[Sulalatus Salatin]] kerajaan ini merupakan kelanjutan dari [[Kerajaan Melayu]] di [[Singapura]], kemudian serangan [[Jawa]] dan [[Siam]] menyebabkan pusat pemerintahan berpindah ke [[Malaka]]. [[Kronik]] [[Dinasti Ming]] mencatat [[Parameswara|Paramisora]] sebagai pendiri Malaka mengunjungi [[Kaisar Yongle]] di [[Nanjing]] pada tahun 1405 dan meminta pengakuan atas wilayah kedaulatannya.<ref>{{cite book|last= Gungwu|first= Wang|title= Only connect!: Sino-Malay encounters|publisher= Eastern Universities Press|year= 2003|id= ISBN 981-210-243-4 }}</ref> Sebagai balasan upeti yang diberikan, [[Kaisar Tiongkok]] menyetujui untuk memberikan perlindungan pada Malaka,<ref name="ASHM">{{cite book|last= Hooker|first= Virginia M.|title= A Short History of Malaysia: linking east and west|publisher= Allen & Unwin|year= 2003|id= ISBN 1-86448-955-3 }}</ref> kemudian tercatat ada sampai 29 kali utusan Malaka mengunjungi Kaisar Tiongkok.<ref>{{cite book|last= Cleary|first= Mark|coauthors= Kim Chuan Goh|title= Environment and development in the Straits of Malacca|publisher= Routledge|year= 2000|id= ISBN 0-415-17243-8 }}</ref> Pengaruh yang besar dari relasi ini adalah Malaka dapat terhindar dari kemungkinan adanya serangan Siam dari utara, terutama setelah Kaisar Tiongkok mengabarkan penguasa [[Kerajaan Ayutthaya|Ayutthaya]] akan hubungannya dengan Malaka.<ref name="Kong"/> Keberhasilan dalam hubungan diplomasi dengan Tiongkok memberi manfaat akan kestabilan pemerintahan baru di Malaka, kemudian Malaka berkembang menjadi pusat perdagangan di Asia Tenggara, dan juga menjadi salah satu pangkalan armada Ming.<ref name="ISAS"/><ref name="Wink">{{cite book|last= Wink|first= André|title= Indo-Islamic society, 14th-15th centuries|publisher= BRILL|year= 2004|id= ISBN 90-04-13561-8 }}</ref>
Laporan dari kunjungan Laksamana [[Cheng Ho]] pada 1409, mengambarkan [[Islam]] telah mulai dianut oleh masyarakat Malaka,<ref name="Kong">Yuanzhi Kong, (2000), ''Muslim Tionghoa Cheng Ho: misteri perjalanan muhibah di Nusantara'', Yayasan Obor Indonesia, ISBN 979-461-361-4</ref> sementara berdasarkan catatan Ming, penguasa Malaka mulai mengunakan gelar [[sultan]] muncul pada tahun 1455. Sedangkan dalam [[Sulalatus Salatin]] gelar sultan sudah mulai diperkenalkan oleh penganti berikutnya ''Raja Iskandar Syah'', tokoh yang dianggap sama dengan [[Parameswara]] oleh beberapa sejarahwan.<ref name="ISAS"/> Sementara dalam [[Pararaton]] disebutkan terdapat nama tokoh yang mirip yaitu ''Bhra Hyang Parameswara'' sebagai suami dari [[Majapahit|Ratu Majapahit]], [[Suhita|Ratu Suhita]]. Namun kontroversi identifikasi tokoh ini masih diperdebatkan sampai sekarang.
