Kesultanan Melaka
Pendirian

Artikel utama: Parameswara
Lihat pula: Penjarahan Singapura
Setelah dilakukan penelitian sejarah, baik dari buku Sejarah Melayu karya Tun Sri Lanang, buku Hikayat Raja-raja Pasai karya Syekh Nuruddin Raniri, buku Riwayat Negeri Malaka dalam bahasa Portugis karya Barros pada tahun 1553, catatan orang Tionghoa, juga dengan Babad Tanah Jawa Pararaton (raja-raja), dapat diambil kesimpulan bahwa pada permulaan abad ke-14, daerah Tanjung Medini masih perang antara dua kekuatan. Di sana belum ada kerajaan. Akan tetapi, di tanah Jawa, telah muncul kerajaan multikultural Majapahit yang menjadi lawan kuat Siam dalam memperebutkan kekuasaan di Selat Malaka, terutama pada tahun 1331, ketikaGajah Mada mendapat kepercayaan tinggi dari Batara Majapahit. Setelah Gajah Mada naik, digariskanlah politik yang tegas, yaitu memperluas kekuasaannya dan merebut sebuah tanjung yang sering terjadi perang antara penduduk setempat dengan negeri Siam. Majapahit pun menyerang Palembang, Singapura, Brunei, Pasai, sebagian Tembeling, dan kemungkinan juga termasuk Luzon. Padahal, di Singapura saat itu masih berdiri sebuah kerajaan independen.
Dengan jatuhnya kerajaan Melayu Hindu di Singapura karena serangan Majapahit, raja Singapura berangkat melarikan diri dari Singapura. Raja tersebut bernama Permaisura. Mula-mula, bersembunyilah ia ke sebuah kampung di sebelah utara Pulau Singapura. Dari sana, ia menyeberang ke Semenanjung Melayu melalui Johor. Kemudian, terus ke negeri Muar. Dari Muar, diteruskannya perjalanan ke Sungai Ujung, hingga akhirnya ia sampai di Malaka.
Saat itu, ia mendapati penduduk Malaka sudah mulai ramai, baik dari orang Melayu, Arab, Cina, Romawi, Siam, dan lainnya. Kemudian, Sidi Abdul Aziz, seorang ulama yang berasal dari Jeddah, datang ke Malaka, mengajak ia untuk masuk Islam. Ajakan itu diterima. Sidi Abdul Aziz menganjurkan kepada ia untuk mengganti namanya menjadi Sultan Muhammad Syah. Ia memeluk Islam sekitar tahun 1384. Sejak itu, ia resmi menjadi sultan negeri Malaka.
Sementara itu, berdasarkan Sulalatus Salatin dan Suma Oriental Kerajaan ini didirikan oleh Parameswara seorang pangeran yang berasal dari palembang yang melarikan diri karena invasi angkatan laut Majapahit dan Ayutthaya meskipun tidak terucap Ayutthaya. Kronik Dinasti Ming juga mencatat Parameswara sebagai pendiri Malaka mengunjungi Kaisar Yongle di Nanjing pada tahun 1405 dan meminta pengakuan atas daerag kedaulatannya. Sebagai balasan upeti yang diberikan, Kaisar Tiongkok menyetujui untuk memberikan perlindungan pada Malaka, kemudian tercatat ada sampai 29 kali utusan Malaka mengunjungi Kaisar Tiongkok. Pengaruh yang besar dari relasi ini adalah Malaka dapat terhindar dari kemungkinan adanya berbagai serangan terutama Jawa dan Siam, apalagi setelah Kaisar Tiongkok mengabarkan penguasa Ayutthaya akan rencananya terhadap daerah tanjung tersebut. 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.
Laporan dari kunjungan Laksamana Cheng Ho pada 1409, mengambarkan Islam telah mulai dianut oleh masyarakat Malaka, 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. Sementara dalam Pararaton disebutkan terdapat nama tokoh yang mirip yaitu Bhra Hyang Parameswara sebagai suami dari Ratu Majapahit, Ratu Suhita. Namun kontroversi identifikasi tokoh ini masih diperdebatkan sampai sekarang.
Pada tahun 1414 Parameswara digantikan putranya, Megat Iskandar Syah, memerintah selama 10 tahun, kemudian menganut agama Islam dan digantikan oleh Sri Maharaja atau Sultan Muhammad Syah. Putra Muhammad Syah yang kemudian menggantikannya, Raja Ibrahim, mengambil gelar Sri Parameswara Dewa Syah. Namun masa pemerintahannya hanya 17 bulan, dan dia mangkat karena terbunuh pada 1445. Saudara seayahnya, Raja Kasim, kemudian menggantikannya dengan gelar Sultan Mudzaffar Syah.