Abans d'erigir-se el fort Bélgica, hi havia un fort portuguès del segle xvi a la part alta d'un turó a Banda Neira. El 4 de setembre de 1611, Pieter Both, el primer governador general de les Índies Orientals Neerlandeses, va ordenar la construcció d'un nou fort que reforcés el turó que dominava la fortalesa neerlandesa original, el Fort Nassau.[1] Aquest fort va rebre el nom de Bélgica o Nederland, i va acabar coneixent-se com a Fort Bélgica.[2] El fort inicial era una fortificació quadrada modesta a la part alta d'un pujol. L'any 1662, Jan Pieterszoon Coen va ordenar la renovació del fort original, de manera que va ser reemplaçat per un reducte més sòlid que podia allotjar fins a 40 homes.[2][3] A causa dels terratrèmols de mitjan segle xvii, el clima monsònic tropical i la pobresa de la tècnica i dels materials amb què es va construir originàriament, l'estructura es va deteriorar.[4] L'any 1667, el governador Cornelis Speelman va ordenar a l'enginyer Adriaan de Leeuw que tornés a dissenyar i reconstruir el fort. El resultat és el la fortalesa actual, les obres de modificació van començar el 1672 i es van acabar en 1673. El nou Fort Bèlgica es va construir amb pedra portada en vaixell fins a l'illa.[4] El nou disseny estava format per una estructura pentagonal inferior amb cinc bastions en angle i un pentàgon interior més alt amb cinc torres altes circulars, sent l'únic fort d'aquest tipus a les illes Banda. Malgrat que es van gastar 300.000 florins en les modificacions, un armament de 50 canons i una guarnició de 400 homes, el Fort Bèlgica es va rendir a la flota britànica el 1796 sense haver disparat un sol tret.[4] Retornada als neerlandesos el 1803, els britànics van tornar a prendre'l l'any 1810, quan va ser atacat pel capità Cole i els seus homes. Parcialment demolit el 1904, va ser reconstruït de manera incompleta l'any 1919. El 1991 es va restaurar completament el fort, després de l'ordre del general Leonardus Benjamin Moerdani, en aquella època ministre de defensa i Seguretat d'Indonèsia.[3]