V roce 1396 princ jménem Parameswara uprchl z jeho země ze strachu z útočící Majapahit Říše. Přistál v Temaseku, kde zabil místního vládce a usadil se na ostrově, který je nyní znám jako Singapur. O několik let později byl vyhnán armádou ovládanou Thajskem a opět hledal novou zem. Nakonec se přesunul na západní pobřeží Malajsie, kde vznikla Malacca. Legenda říká, že odpočíval pod stromem, když viděl kančila, jak kope jeho lovecké psi do řeky. Prohlásil, že místo je příznivé a rozhodl se postavit obchod a pojmenoval ho po stromě pod kterým odpočíval.
V roce 1414 Parameswara konvertoval k islámu, což vedlo k tomu, že se stal sultánem Malaccy. Město také rostlo v prominentní obchodní půdu pro obchodníky z celé Asie, zejména Indie, Arábie a Číny. Výsledkem toho bylo, že mnoho čínských migrantů se tady usadilo a založilo kulturu Peranakan. Malacca také navázala kontakt s Čínskou Říši přes průzkumníka Zheng He, aby ochránil jejich území před siamskými silami, což bylo ukončeno svatbou mezi sultánem Mansur SHah a Hang Li Poh.
Kolonizace
O sto let později přišli Portugalci, kteří dobyli Malaccu v roce 1511. To byl klíčový moment pro západní kolonizátory, kteří chtěli rozšířit svou říši do Východní Indie. Malacca pod vládou Portugalců stále prosperovala, dokud se neobjevil Holanďan. S pomocí sultána Johora (potomkem sultána Malaccan) Holanďan dobyl přístav a vládl nad ním do roku 1795, kde Malacca byla přenechána Britům za Batavii (Jakartu) v Indonésii. Britská východoindická společnost rozvinula Malaccu a rozšířila jejich vliv všude po Malajsii, čímž si prosadila kontrolu nad obchodním průmyslem a zaměstnala guvernéry, aby vládli státům. Společnost byla nahrazena přímou správou přímo z Korunní kolonie. Nakonec Malacca, společně se zbytkem Malajsie, přijala nezávislost v roce 1957, což je připravilo na budoucnost, která je nyní.
Legenda o Puteri Gunung Ledang
Další slavná městská legenda v Malacce se točí okolo Puteri Gunung Ledangy nebo Princezny Mount Ledang. Místní lidé se domnívají, že princezna byla víla, kterou si chtěl sultán vzít. Položila mu několik podmínek, přičemž jedna z nich byla naplnit plnou sklenici srdci komárů a slz panen. Poslední podmínka však vyžadovala šálek synovy krve. Tohle sultán, ale splnit nemohl (říká se, že o tom přemýšlel, ale princezna ho pokárala) a bohužel se vzdal naděje, že si ji vezme.
Legenda o Hang Tuah
Během vlády sultána Malacca vzniklo mnoho legend a příběhů, které jsou zaznamenány v „Sejarah Melayu“ nebo Letopisech o malajské historie. Nejznámější legendou je příběh o Hang Tuah, což byl malajský bojovník s vynikajícími dovednostmi a loajalitou k sultánovi. Říká se, že jednoho dne úředníci žárlili na to, že si sultán oblíbil Hang Tuaha. Vymysleli si proto příběh, že se Hang vyspal s nejoblíbenější manželkou sultána. Rozhořčený sultán hned nařídil, aby byl Hang Tuah usmrcen. Avšak ministr Tun Perak ho u sebe schoval a věřil v jeho nevinu. Jeden z Hangových přátel (Hang Kasturi) byl zarmoucen, když slyšel o „smrti“ jeho přítele. Chytil ho z toho strašlivý vztek a zabil několik úředníků. Nebyl nikdo, kdo by mohl soupeřit s jeho zuřivostí, a dokonce i sultán ze strachu utekl z paláce. Nakonec Tun Perak přivedl Hang Tuah zpátky do září reflektorů a sultán mu odpustil a nařídil mu, aby popravil Hang Kasturi. Hang Tuah poslechl a navzdory prosbám Hanga Kasturi bojovali měsíc, než Kasturi prohrál. Hang Kasturi byl poté přejmenován na „Hang Jebat“, což znamená „shnilý zápach“, zatímco Hang Tuah byl oslavován po celém světě.