Malacca was founded by Parameswara, a Srivijayan prince who left Sumatra in 1396. 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 the very place that he was sitting. 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. Old illustrations of the scene where the mousedeer kicks the dog shows the dog falling on its back into the river, hence the inspiration.
Parameswara converted to Islam in 1414 and changed his name to "Raja Iskandar Shah". What started as a fishing village then grew into the most important port in the region, attracting traders from Java, India, Arabia and China, and served as a stopping point for China-India trade during the two monsoon periods. Mass settlement of Chinese, mostly from the imperial and merchant fleet occurred during the reign of Parameswara, occurred in the vicinity of the Bukit China ("Chinese Hill") area, which had among the best Feng Shui (geomancy) in Malacca then. Sultan Iskandar Shah died in 1424, and was succeeded by his son, Sri Maharaja also called Sultan Muhammad Shah.
Unfortunately, the prosperity of Malacca attracted the invasion of the Siamese. Attempts in 1446 and 1456, however, were warded off by Tun Perak, the then Chief Minister. The development of relations between Malacca and China was at that time a strategic decision to ward off further Siamese attacks.
Because of its strategic location, Malacca was an important outpost for Zheng He's spectacular exploration fleet. To enhance relations, Hang Li Po, allegedly a princess of the Ming Emperor of China, arrived in Malacca, accompanied by 500 attendants, to marry Sultan Mansur Shah who reigned from 1456 until 1477. Her attendants married the locals and settled mostly in Bukit China (Bukit Cina).
A cultural result of the vibrant trade was the expansion of the Peranakan people, who spread to other major settlements in the region.
During its heyday Malacca was a powerful Sultanate which extended its rule over the southern Malay Peninsula and much of Sumatra. Its rise help to hold off the Thai's southwards encroachment and arguably hasten the decline of the rival Majapahit Empire of Java. Malacca was also central in the spread of Islam in the Malay Archipelago.