À moins de 100 mètres du palais du sultanat, se trouve l'une des plus anciennes ruines d'origine européenne en Asie : elle s'appelle A Famosa, et c'est une forteresse construite pendant la période du colonialisme portugais. De nos jours, seule la partie où s'ouvrait la Porta de Santiago, l'une des portes d'entrée de l'avant-poste, a survécu. En 1511, la flotte portugaise commandée par Afonso de Albuquerque débarque, attaque et défait les forces du Sultanat de Malacca, le plus ancien de Malaisie et, à l'époque, le plus puissant royaume de la péninsule malaise. Le commandant Albuquerque a demandé d'urgence la construction d'une forteresse construite autour d'une colline qui, à l'époque, se trouvait face à la mer (aujourd'hui, le rivage s'est déplacé de plusieurs centaines de mètres). Albuquerque pensait en effet que Malacca deviendrait un port important pour relier l'Empire du Portugal à la route des épices vers la Chine. À la même époque, d'autres flottes portugaises ont conquis des endroits comme Macao, en Chine, et Goa, en Inde, dans le même but de créer des ports satellites où les navires portugais transitant entre le Portugal et la Chine pourraient accoster en toute sécurité pour se ravitailler et s'abriter. Le détroit de Malacca, dominé par la ville du même nom, était d'une importance vitale pour assurer le passage en toute sécurité des navires européens entre l'Occident et l'Extrême-Orient. Le pouvoir qui dominait Malacca aurait exercé un contrôle sur l'ensemble du détroit grâce à sa position stratégique. La forteresse, dans la vision du capitaine portugais, devait naturellement être l'avant-poste pour garder une ville d'une telle importance. Il a été construit en peu de temps avec de hauts murs, des tours et quatre portes d'entrée fortifiées. Chaque tour avait un entrepôt de munitions, il y avait une résidence pour le capitaine et pour les officiers en service. Le village actuel était situé, selon les plans médiévaux encore en usage chez les Portugais, à l'intérieur des murs de la forteresse. Naturellement, au fur et à mesure que l'importance du port malaisien s'est accrue, ainsi que la population d'habitants et de commerçants qui s'y arrêtaient, des maisons ont bientôt commencé à être construites bien en dehors du périmètre des murs. La forteresse a changé de mains en 1641 lorsque les Hollandais, qui étaient déjà actifs en Indonésie avec leur propre Compagnie des Indes orientales, ont vaincu leurs rivaux européens avec l'aide de franges malaisiennes hostiles à la domination portugaise. Le fort a été préservé car il était encore d'un usage stratégique, bien qu'endommagé par des tirs de canon. Au-dessus des quatre portes d'entrée, les Hollandais ont sculpté un bas-relief avec le logo de la Compagnie néerlandaise des Indes orientales. En 1806, les Britanniques ordonnent la destruction du fort.
