Lang voordat Nederlanders op Ambon arriveerden, hadden de Portugezen zich hier al gevestigd. Aan de baai van Ambon bouwde de Portugezen hun eerste versterking in 1576. Dit werd rond 1580 vervangen door een beter fort, met vier bastions, dichter bij het water. Het werd Forte de Nossa Senhora da Anunciada genoemd door de Portugezen en stond lokaal bekend als Kota Laha. Op 23 februari 1605 wist Admiraal Steven van der Hagen deze vesting in te nemen voor de VOC, zonder ook maar een schot te lossen. Uit dankbaarheid voor deze overwinning, werd het fort Victoria hernoemd. Het werd de zetel voor het eerste Nederlandse territorium in Indië, het Gouvernement Amboina. Frederik de Houtman (1605-1611) werd de eerste gouverneur. Het fort vormde aanvankelijk de hoofdzetel van de VOC in Azië, totdat Fort Oranje op Ternate, en later Batavia, deze rol overnam.
Fort Victoria werd meerdere malen herbouwd en versterkt. Zoals opgetekend in 1627 had het fort aanvankelijk twee poorten en vier bastions, waarvan de bastions aan de landzijde groter en hoger waren uitgevoerd. Het geheel werd omringd door een anderhalve meter diepe natte gracht. Binnen de muren bevonden zich de onderkomens voor het VOC personeel en ruimtes voor de opslag van handelswaar en wapens. In 1643, 1672 en 1673 deden zich aardbevingen voor die het fort dermate zwaar beschadigden dat op zeker moment werd overwogen de positie te verlaten en een geheel nieuw fort bij Laha aan de overzijde van de baai op te richten. Ten opzichte van die plek werd de positie van Fort Victoria als minder strategisch en moeilijker te verdedigen gezien. Uiteindelijk besloot de VOC toch dat het bouwen van een nieuw fort te duur zou worden en werd Fort Victoria weer van de ruïnes herrezen.
Ook gedurende de achttiende bleven aardbevingen herhaaldelijk schade toe brengen aan het fort en werden vervolgens steeds weer herstelwerkzaamheden uitgevoerd. Tijdens het gouverneurschap van Bernardus van Pleuren (1775-1785) werden grootschalige herstel
en uitbreidingswerkzaamheden uitgevoerd. Met zeven bastions en een hoornwerk omgeven door een gracht kreeg het verdedigingswerk toen de polygonale vorm die vandaag nog gedeeltelijk is terug te zien. Na deze ingrijpende verbouwing werd het fort Nieuw Victoria genoemd
Naast het fort was een aanzienlijke nederzetting gegroeid. In 1683 woonde er, het garnizoen meegerekend, 770 Europeanen. Al het VOC functionarissen meegerekend woonde er tussen 1726-1730 ongeveer 1070 Europeanen in het Gouvernement Amboina. Na 1656 onderhield de VOC een macht van 600 soldaten op de Ambon-eilanden. De helft van hen waren op fort Victoria gestationeerd, de rest verspreid over de 18 kleinere versterkingen. Echte belegeringen heeft het fort nooit doorstaan. De Engelsen namen het oorlogen in 1795 zonder tegenstand over.
Waarschijnlijk zijn delen van de bastions en de vestingmuren aan de landzijde na de zware aardbeving van 1898 gesloopt en de grachten gedempt. Ook Amerikaanse bombardementen tijdens de Tweede Wereldoorlog brachten zware schade toe. Wat resteert zijn delen van het waterfront en het hoornwerk. De stadspoort werd herhaaldelijk herbouwd. In het fort resteren het fraaie in het halfbastion Zeelandia ingebouwde 18e-eeuwse kruithuis en een sober verblijf in het bastion Groningen. De overige bebouwing bestaat uit vrij recent gebouwde kantoren, barakken, woonhuizen en opslagplaatsen welke gebruikt worden door een onderdeel van het Indonesische leger, dat op het fortterrein is gelegerd.
