Melaka sebagai sebuah negeri bermula dengan penubuhannya sebagai kerajaan Melaka Darul Azim dalam tahun 1400 oleh Sri Parameswara, yang kemudian bergelar Sultan Muhammad Iskandar Shah 1.
Parameswara adalah Raja Johor yang beragama Hindu. Dalam tahun 1400, baginda meninggalkan Johor untuk membentuk sebuah negeri baru. Tujuannya adalah untuk mengelakkan diri daripada dibunuh oleh Raja Siam.
Lima tahun sebelum itu, Parameswara telah menghukum bunuh panglima perang Raja Siam yang cuba membunuhnya dan merampas Singapura dari tangannya.
Parameswara memberikan nama Melaka kepada kerajaan barunya yang didirikan di daerah Bertam, Johor, setelah melihat anjing buruannya ditendang ke dalam sungai oleh seekor pelanduk.
Baginda berasa bumi Bertam amat bertuah lalu membuat keputusan menjadikan Bertam sebagai negeri Melaka Darul Azim. Melaka dinamakan sempena pokok Melaka yang berdiri gagah di belakang baginda semasa melihat kejadian ajaib itu.
Dengan bantuan Maharaja China yang melindungi Melaka dari serangan Siam, Parameswara dan waris-warisnya telah berjaya menjadikan Melaka sebuah pusat perdagangan ternama di Asia dan di dunia bagi menggantikan Johor.
Dalam tahun 1414, Parameswara telah memeluk agama Islam yang dibawa oleh pendakwah dari Kedah, Kelantan, Brunei dan Arab. Baginda mengambil gelaran Arab Sultan dan menukar namanya kepada Sultan Muhammad Iskandar Shah 1.
Selepas Parameswara, Melaka diperintah oleh anaknya Sultan Muhammad Shah 1 (1424-1444), dua anak Sultan Muhammad Shah 1 iaitu Sultan Ibrahim Shah (1444-1446) dan Sultan Muzaffar Shah 1 (1446-1459), dan anak Sultan Muzaffar Shah 1 iaitu Sultan Mansur Shah 1 (1459-1477).
Seterusnya, Sultan Alauddin Riayat Shah 1 (1477-1488) iaitu anak Sultan Mansur Shah 1, dan Sultan Mahmud Shah 1 (1488-1511) iaitu anak Sultan Alauddin Riayat Shah 1.
Dalam tahun 1511, Portugis telah menyerang dan menakluk Melaka. Sultan Mahmud Shah 1 telah berundur ke Johor dan menjadi Sultan Johor semula.
Portugis telah diusir oleh Belanda dalam tahun 1641, dengan bantuan Sultan Abdul Jalil Shah 3 Johor.
Dalam tahun 1824, British telah mengambil alih Melaka dari Belanda.
Britain telah memberi kemerdekaan kepada Melaka pada Ogos 31, 1957. Melaka menjadi sebuah negeri dalam Persekutuan Malaysia dengan seorang Yang Dipertua Negeri (Gabenor) sebagai ketua negerinya.
Sultan Johor pada masa itu, iaitu Sultan Ibrahim, mengambil keputusan untuk tidak menggabungkan Melaka ke dalam Johor.
