Long before the Dutch arrived, the Portuguese settled on Ambon. The first Portuguese stronghold on the bay of Ambon was built in 1576. Around 1580 this structure was replaced by a better fort with four bastions, closer to the shore. It was named Forte de Nossa Senhora da Anunciada in Portuguese and was locally known as Kota Laha. On February 23 1605 the Portuguese surrendered this fort to VOC Admiral Steven van der Hagen without a shot being fired. In gratitude for what seemed to have been a god-given victory, the fort was renamed Victoria by the Dutch. It became the seat of the first Dutch territory in the Indies, the Government of Amboina. The first to hold the position of governor was Frederik de Houtman (1605-1611). For the years that followed the fort served as the general administrative center for the VOC in Asia, before it was shifted first to Fort Oranje in Ternate and later to Batavia.
Fort Victoria was rebuild and strengthened multiple times. As described in 1627, initially the fort had two gates and four bastions, with the bastions facing the landside being bigger and higher. A one and a half meter deep moat filled with water surrounded the structure. Within the walls there were spaces to store trade goods and weapons and accommodations for people in service of the VOC. Earthquakes that took place in 1643, 1672 and 1673 damaged the structure till such extent that it was considered to leave Fort Victoria and built a whole new fort on the opposite side of the bay at Laha. The position of Fort Victoria was seen as less strategic and more difficult to defend, due to the hills surrounding the structure. In the end however, the VOC judged that building a new fort was too expensive and Fort Victoria was raised from the ruins.
Also throughout the eighteenth century earthquakes caused damage to the structure and subsequently repair works were conducted. During the reign of Governor Bernardus van Pleuren (1775-1785), the structure was extended to the polygonal shape, with seven bastions a hornwork and a moat, which is still partly visible today. It was after this works were finished that the fort became known as Nieuw Victoria.
Close to the fort a considerable residential town has grown. In 1683 there were 770 Europeans living in the town, including the garrison; the number of Company officials in the whole Government of Amboina added up to 1070 people in the period of 1726-1730. After 1656 the Company maintained a force of around 600 soldiers in the Ambon Islands, half of whom were billeted in Victoria Castle; the other half were spread across 18 smaller strongholds. The fort has never been sieged. Without any resistance, the English took over the fort during the Napoleonic wars in 1795. Most likely the bastions and parts of the walls have been torn down after the earthquake of 1898. Also American bombardments during the second world war caused heavy damage. What remains are parts of the walls facing the bay and the hornwork. The gate has been restored several times. Within the fort, the eighteenth century powderstorage within the half-bastion Zeelandia and a room within bastion Groningen are still intact. Other buildings are from more recent date. The area still has a military function, being used today by the Indonesian army.