Before the arrival of the first Sultan, Malacca was a simple fishing village inhabited by local Malays. Malacca was founded by Parameswara, the last Raja of Singapura (Singapore) following a Majapahit attack in 1377. He found his way to Malacca. 1400 where he found a good port accessible in all seasons and on the strategically located narrowest point of the Malacca Straits. Established by the Malay ruler Parameswara, the Sultanate of Malacca was first a Hindu Kingdom in 1402 and later converted to Islam with the marriage of the princess of Pasai in 1409. Centered in the modern town of Malacca, the sultanate stretched from Muslim Malay settlements of Phuket Province, Satun, Pattani bordering the Ayutthaya Kingdom of Siam (Thailand) in the north to Sumatra in the southwest. The Portuguese invaded its capital in 1511 and in 1528.

In the aftermath the Sultanate of Johor was established by the Malaccan prince Alauddin Riayat Shah II as a successor state. According to a popular legend, Parameswara was resting under a tree near a river while hunting, when one of his dogs cornered a mouse deer. In self-defence, the mouse deer pushed the dog into the river. Impressed by the courage of the deer, and taking it as a propitious omen of the weak overcoming the powerful, Parameswara decided on the spot to found an empire on that very spot. He named it 'Melaka' after the tree under which he had taken shelter. Another version of the story says that Parameswara chose the name 'Malacca' from the Tamil word 'mallakka' which means upside down or on ones back. An old illustration of the scene where the mousedeer kicks the dog shows the dog falling on its back into the river, hence the inspiration.