Parameswara
Pada tahun 1411, Parameswara, beserta istri dan anaknya, yang juga diikuti oleh 540 orang kerajaan, berangkat ke Tiongkok bersama Laksamana Cheng Ho. Keberangkatan itu untuk memberi penghormatan kepada Kaisar Yongle. Ketika utusan dari Malaka memberi penghormatan kepada Kaisar Tiongkok, kaisar memuji Parameswara dan mengakuinya sebagai penguasa sah di Malaka.
Kaisar Yongle kemudian memberikan Parameswara tanda kehormatan, sutra dan payung kuning sebagai simbol kerajaan, dan juga surat penunjukan Parameswara sebagai penguasa Malaka. Malaka kemudian diakui sebagai kerajaan oleh Kaisar Tiongkok. Utusan kembali ke Malaka bersama-sama armada Laksamana Cheng Ho, orang China pertama yang berlayar dan menjelajahi daerah di wilayah selatan.
Sejarah Tiongkok menyebutkan bahwa pada tahun 1414, putra penguasa pertama Malaka mengunjungi Ming untuk memberitahu mereka bahwa ayahnya telah meninggal. Parameswara telah digantikan oleh putranya, Megat Iskandar Syah yang kemudian memerintah Malaka sampai tahun 1424.
Beberapa dekade setelah berdirinya Kerajaan Malaka, kota itu berkembang menjadi pelabuhan perdagangan internasional yang digembar-gemborkan sebagai masa keemasan Bangsa Melayu. Ketika itu ada 80 bahasa yang digunakan di Malaka. Kota itu menjadi pelabuhan penting di timur jauh selama abad ke-16. Sehingga penulis Portugis Tome Pires pernah mengatakan: ""Siapapun yang menguasai Malaka maka
dia akan memiliki Venesia"". Malaka merupakan Kesultanan Melayu yang baru, sebagai basis utama dalam melanjutkan perjuangan bersejarah pendahulunya: Singapura dan Sriwijaya, terhadap musuh mereka yang berbasis di Jawa. Pada pertengahan abad ke-15, Majapahit tak mampu lagi mengontrol naiknya kekuatan Malaka yang mulai mengendalikan Selat Malaka dan memperluas
pengaruhnya ke Sumatera. "Malay Annals" mencatat bahwa pada puncak kekuatannya, setelah pengangkatan Sultan Mansur Shah pada tahun 1459, wilayah Malaka menguasai sebagian besar Semenanjung Malaya, Kepulauan Riau, dan sebagian pantai timur Sumatera yaitu Indragiri, Kampar, Siak, Rokan, Haru, dan Siantan. Malaka terus memperluas wilayahnya hingga akhir tahun 1506 ketika mereka menaklukkan Kelantan.
Kemakmuran Malaka sebagai pelabuhan internasional telah mengubah konstelasi politik di seluruh Kepulauan Melayu, dan keberhasilannya dikagumi oleh raja-raja dari kerajaan tetangga. Sebagai tempat penyaluran barang terbesar, Malaka menarik pedagang muslim dari berbagai belahan dunia dan kemudian menjadi pusat penyebaran Islam ke seluruh Kepulauan Melayu. Proses Islamisasi di wilayah sekitar Malaka
secara bertahap terjadi secara intensif antara abad ke-15 dan 16 melalui pusat studi di Upeh, di tepi utara Sungai Malaka. Islam menyebar dari Malaka ke Jambi, Kampar, Bengkalis, Siak, Aru, dan Kepulauan Karimun di Sumatera, di banyak Semenanjung Melayu, Jawa, dan bahkan Filipina. "Malay Annals" bahkan mengungkapkan bahwa pada masa itu pengadilan Malaka dan Pasai saling mengajukan pertanyaan teologis dan
masalah satu sama lain. Berdasarkan catatan sejarah dua di antara sembilan orang penyebar Islam di tanah Jawa (Wali Songo), yakni Sunan Bonang dan Sunan Kalijaga, pernah belajar di Malaka. Ekspansi Islam ke pedalaman Jawa pada abad ke-15, menyebabkan menurunnya kekuasaan musuh lama Malaka, yakni Hindu-Majapahit, sebelum akhirnya menyerah pada pasukan muslim lokal yang muncul di awal abad ke-16.