Syahdan apabika mangkat Raja Besar Muda, puteranya yang bernama Raja Tengah menggantikan kedudukan sebagai raja. Seterusnya pemerintahan dipegang putera Raja Tengah yang bernama Raja Kecil Besar. Dan semasa raja inilah menurut ceritanya, beliau terkenal sebagai seorang raja yang adil bijak-bestari. Raja inilah yang mula-mula masuk Islam, maka bagindapun bergelar dengan nama Sultan Muhammad Syah. Sultan inilah yang meletakkan adat Melayu seperti warna kuning yang menjadi baju dan destar raja-raja. Kemudian larangan membuat rumah kepada rakyat yang mempunyai peranginan dan tiangnya dan tiangnya beralas tiada terletak ke tanah (tiangnya ditanam ke tanah). Kemudian juga terlarang kepada rakyat untuk membuat rumah berpelayan dan berpelantaran. Demikian juga dalam pembuatan perahu, terlarang memiliki tingkap dan berpengadapan. Kemudiannya terlarang juga kepada hamba rakyat untuk bergelang kaki emas keranchang, walau kaya sekalipun; melainkan mendapat anugerah raja. Kemudian ditetapkan juga di dalam adat yang boleh datang menghadap ke Balai Rong adalah anak-anak raja jua. Sedangkan Raja Muda, Bendahara, Temenggung, Indera Bungsu dan segala menteri-menteri daripada raja-raja hanya dapat menghadap Sultan di Seri Balai. Sultan Muhammad Syah berkuasa selama 67 tahun. Sejak saat itulah istilah RAJA berganti dengan panggilan SULTAN.
Sultan terakhir sebagai kerajaan yang merdeka ialah Sultan Mahmud Syah I. Pada saat ini kerajaan Melaka diserang oleh Portugis. Dan Portugis berhasil mengalahkan serta menduduki Melaka dari tahun 1511 -1641 M.
Kemudiannya Melaka menjadi pusat pemerintahan kesultanan yang menguasai sebagian wilayah di Selat Melaka termasuklah wilayah-wilayah Pesisir Timur Sumatera. Sultan-sultan Melaka beriktiar sekuat tenaga untuk menjadikan wilayahnya sebagai pusat pemerintahan, pusat perkembangan Islam dan kota dagang di Asia Tenggara serta berhasil pula menjadi pusat peradaban Melayu. Keberhasilan Melaka menjadi pusat peradaban dan tamadun Melayu berkat usaha dari Sultan yang dibantu oleh para laksemana seperti Hang Tuah yang kemudian mengeluarkan ungkapan terkenal :
Tuah sakti hamba negeri,
Esa hilang dua terbilang,
Patah tumbuh hilang berganti,
Takkan Melayu hilang di bumi.
Kepemimpinan Melaka zaman kesultanan ini ditandai dengan terbitnya Undang-undang Melaka yang antara lain menetapkan adat mempunyai kedudukan yang penting dalam menentukan keadilan di dalam megeri. Kemudian pengaruh Islam juga semakin besar, tidak saja dalam pemerintahan tapi juga dalam kehidupan kemasyarakatan.
Sultan sebagai penguasa tertinggi dalam pemerintahan dan agama. Penggantian Sultan atas dasar keturunan dari pihak ayah, tidak boleh dipindahkan. Dan setelah mendapat persetujuan dari pembesar-pembesar istana lainnya. Selanjutnya disebutkan pula bahwa Datuk Bendahara sebagai wakil Sultan atau Perdana Menteri. Laksemana sebagai penguasa di laut. Penghulu Bendahari berfungsi sebagai pembantu Bendahara. Jabatan lainnya ialah Khalifah, Amir, Syarif dan Qadhi.
Tersebut pula suatu pertelingkahan di antara raja-raja itu adanya, yaitu pertelingkahan antara Sultan Mahmud dengan puteranya Sultan Ahmad Syah yang mengakibatkan perpecahan kepada enam keturunan raja Melayu di dalam Melaka. Kemudiannya berpindahlah kerajaan ke Johor, dari Johor terus ke Riau.
