Ani ne 100 metrů od Paláce Sultanát, je jedním z nejstarších zřícenin Evropského původu v Asii: jeho jméno je Famosa, a to je pevnost postavená v období portugalského kolonialismu. Do dnešního dne přežila pouze část, kde se otevřela Porta de Santiago, jedna ze vstupních bran základny. Dveře a staré stěny, které jej podporují, lze navštívit volně během vaší chůze ulicemi Malacca.V roce 1511, portugalská flotila pod velením Afonso de Albuquerque přistál, zaútočil a porazil síly Sultanát Malacca, nejstarší v Malajsii a v té době nejmocnější království na Malajský Poloostrov. Velitel Albuquerque naléhavě vyžadoval výstavbu pevnosti postavené kolem kopce, který byl v té době před mořem (dnes se břeh posunul o několik set metrů). Albuquerque věřil, že Malacca se stane důležitým přístavem pro spojení portugalské Říše s cestou koření do Číny. Ve stejném období dalších portugalského loďstva dobyl místech, jako jsou Macau, v Číně a Goa, v Indii, se stejným účelem vytvoření satelitní porty, do kterých se portugalské lodě plující mezi Portugalskem a Čínou by mohla doku bezpečně na dodávky a přístřeší. Úžiny Malacca, dominuje právě tím, že město stejného jména, bylo životně důležité zajistit bezpečný průchod Evropských lodí mezi Západem a dálným Východem. Moc, která dominovala Malacce, by díky své strategické poloze vykonávala kontrolu nad celým průlivem. Pevnost, ve vizi portugalského kapitána, by samozřejmě měla být základnou střežící město takového významu. Byl postaven v krátké době s vysokými zdmi, věžemi a čtyřmi opevněnými vstupními branami. Každá věž měla sklad munice, byla zde rezidence pro kapitána a pro důstojníky ve službě. Skutečné město se nacházelo podle středověkých schémat, které se stále používají mezi Portugalci, uvnitř zdí pevnosti. Samozřejmě, s rostoucí význam Malajského přístavu, stejně jako populace obyvatel a obchodníků, kteří tam zůstali, brzy se domky začaly stoupat i mimo obvod městských hradeb. Pevnost změnil majitele v roce 1641, když vstoupili, holandština, již působí v Indonésii s jejich vlastní společnosti v Indii, který vyhnal Evropské soupeři pomohl tím, Malajský okraji nepřátelské portugalské pravidlo. Pevnost byla zachována jako stále strategická užitečnost, i když byla poškozena dělovými bitvami. Nad čtyřmi vchodovými dveřmi vytesali Nizozemci basreliéf s logem nizozemské Východoindické společnosti. V roce 1806 Britové nařídili zničení pevnosti.
