Ani 100 metrov od paláca sultanátu sa nachádza jedna z najstarších ruín európskeho pôvodu v Ázii: jej názov je Famosa a je to pevnosť postavená v období portugalského kolonializmu. Do súčasnosti prežila iba časť, v ktorej sa otvorila Porta de Santiago, jedna zo vstupných brán základne. Dvere a staré múry, ktoré ju podporujú, je možné voľne navštíviť počas prechádzky ulicami Malacca.In 1511, portugalská flotila, ktorej velil Afonso de Albuquerque, pristála, zaútočila a porazila sily sultanátu Malacca, najstaršieho v Malajzii a v tom čase najsilnejšieho kráľovstva na Malajskom polostrove. Veliteľ Albuquerque naliehavo požadoval výstavbu pevnosti postavenej okolo kopca, ktorý bol v tom čase pred morom (dnes sa Pobrežie presunulo niekoľko sto metrov). Albuquerque veril, že Malacca sa stane dôležitým prístavom na spojenie portugalského impéria s cestou spice do Číny. V tom istom období dobyli ďalšie Portugalské flotily miesta, ako napríklad Macau, Čína a Goa, India, s rovnakým cieľom vytvoriť Satelitné prístavy, do ktorých by Portugalské lode prechádzajúce medzi Portugalskom a Čínou mohli bezpečne dokovať zásoby a prístrešie. Úžina Malacca, ktorej dominovalo presne mesto s rovnakým názvom, mala zásadný význam na zabezpečenie bezpečného prechodu európskych lodí medzi Západom a Ďalekým východom. Sila, ktorá dominovala Malacca, by vďaka svojej strategickej polohe vykonávala kontrolu nad celým prielivom. Pevnosť, vo vízii portugalského kapitána, by samozrejme mala byť základňou strážiacou mesto takého významu. Bol postavený v krátkom čase s vysokými múrmi, vežami a štyrmi opevnenými vstupnými bránami. Každá veža mala sklad pre muníciu, pre kapitána a pre dôstojníkov v službe bolo bydlisko. Skutočné mesto sa nachádzalo podľa stredovekých schém, ktoré sa stále používajú medzi Portugalcami, v stenách pevnosti. Samozrejme, s rastúcim významom Malajského prístavu, ako aj obyvateľov obyvateľov a obchodníkov, ktorí tam zostali, čoskoro začali domy dobre stúpať mimo obvodu mestských hradieb. Pevnosť zmenila ruky v roku 1641, keď vstúpili do holandčiny, ktorá už pôsobí v Indonézii s vlastnou spoločnosťou Indies, ktorá vyhnala európskych súperov, ktorým pomohli Malajské okraje nepriateľské voči portugalskej vláde. Pevnosť sa zachovala ako stále strategická užitočnosť, hoci bola poškodená kanónovými bitkami. Nad štyrmi vstupnými dverami Holanďania vyrezali basreliéf s logom holandskej Východoindickej spoločnosti. V roku 1806 Briti nariadili zničenie pevnosti.
