In 1396, Parameswara and his followers from Temasik established a settlement at Bertam near the estuary of the Melaka River. According to legend, one day, Parameswara went hunting with his followers. He stopped to rest under a tree by the river and witnessed an unusual display of courage by a mouse-deer that kicked one of the hunting dogs into the river. Inspired by the mouse deer's courage, he freed the animal and decided to make his kingdom in this auspicious land. He named it 'Melaka' after the tree he had earlier rested under.

Towards the end of the 15th century, Melaka had become a renowned empire and till today, the legends and folk stories that sprung from that era are cherished and remembered by Malaysians.