Melaka owes its existence to the rise of the port of Melaka in the 15th century. The State of Melaka served as a hinterland to this port. While the founding of Melaka is shrouded by lack of historical evidence, there is some evidence to suggest that Melaka was founded by Parameswara, a Hindu prince from Palembang/Sumatra, around the year 1400. Legend has it that when Parameswara reached Melaka from Muar, he sat down under a tree for a rest. While resting he saw something strange. A mousedeer (known locally as 'pelanduk'), which was being chased by a dog, suddenly turned around and attacked its pursuer, putting it to flight. Impressed by the bravery of this tiny, docile animal, Parameswara decided there and then, that, that site would be the site of his new kingdom. He decided to call his new kingdom Melaka after the name of the tree under which he was resting. During the course of the next hundred years Melaka developed as the most important entreport port in this part of the world.

Besides its growth as an important port, Melaka also played a major role in the spread of Islam in this region. Historians have many theories as to how Islam came to this part of the world. Professor Treggoning, a former lecturer in history at the University of Singapore and a respected authority on the history of South East Asia, has suggested that Islam came to Melaka from China. Other authorities believe that Arab traders from the Middle East spread it to this part of the world. There are also suggestions that Islam came to Melaka from Arabia via India. Whatever the case may be, one thing is certain. Melaka became the focal point for the spread of Islam in this region when Parameswara, the founder of Melaka, converted to Islam, on his marriage to a princess from Pasai in Indonesia.

During the reign of Parameswara and the Sultans that followed, Melaka continued its territorial growth and extended its economic sphere of influence. A major part of the Malay Peninsula and parts of the Malay - Indonesian archipelago came under its direct or indirect control through conquests, marriages and trade alliances. China was the most powerful country in Asia at that time, and Melaka's good relations with China gave it the recognition and security it needed, to enable it to prosper. The success of Melaka as a port city helped the Malays regain their status as commercial intermediary for the region, which for a long time was in the hands of the Kingdom of Sri Vijaya, followed by the Majapahit Empire.

Melaka was ruled by a structured and hierarchical pyramid system. The apex of the pyramid was the Sultan. Below him were the Four Higher Council Members (Pembesar Berempat), which comprised of the Bendehara (Prime Minister), the Temenggung (Minister of Home Affairs), the Penghulu Bendahari (Minister of Finance) and the Laksamana (Admiral / Minister of Defence)

Melaka's strategic location in Malay-Indonesian archipelago, both commercially and militarily, attracted major powers of the day, looking to extend their sphere of influence in the region, and become major players in the lucrative spice trade.

In AD 1446 and again in AD 1456 the Siamese made attempts to conquer Melaka but they were thwarted.

Next came the Portuguese led by Alfonso de Albuquerque. The Portuguese, a major European naval power of the day, conquered Melaka in spite of the tough resistance by the natives.

During this era of European colonization, Melaka became a pawn in the midst of bitter European political and economic rivalry. The Dutch, another major maritime and economic powerhouse, captured Melaka from the Portuguese in 1641. The Dutch ruled Melaka from 1641-1675. They tried to re-establish Melaka's importance as an entrepot port but as much as they tried they were unable to do so.. This was due to the fact that the East - West spice trade route was by this time firmly under the control of the British, who had a string of ports under its control stretching from Europe to Asia.

The conflicts among the super-powers of that period played a major role in the destiny of Melaka The English East India Company took control of Melaka from the Dutch during the period of the Napoleonic Wars, to prevent it falling into French hands. By the terms of the Treaty of Vienna of 1818 which marked the end of the Napoleonic wars in Europe, Melaka was returned to the Dutch.

In 1824 the British and the Dutch signed the Anglo-Dutch Treaty. One of the terms of this treaty was the demarcation of their respective spheres of influence in the Malay-Indonesian archipelago. As a result Melaka was handed over to the British in exchange for Bencoolen in Sumatra.