De VOC veroverde in 1772 het Hindoeïstische vorstendom Blambangan in de uiterste oosthoek van Java. Haar hoofdvestiging bevond zich aanvankelijk in Oeloepampang, maar verhuisde in 1790 naar Banjoewangi aan Straat Bali. Hier werd een eenvoudig stenen blokhuis en een strafkolonie gebouwd. Kapitein van de genie J.Schmaltz ontwierp in 1801 een groot fort, dat het blokhuis moest vervangen maar nooit werd gebouwd. Banjoewangi werd in 1811 het eindpunt van de Grote Postweg van gouverneur generaal Daendels. Het blokhuis werd versterkt. Tijdens het Engelse bestuur (1811-1816) werd het gezien als een klein fort met 150 soldaten. Er werd een aanval van zeerovers afgeslagen.
Na de terugkeer van de Nederlanders bleef het fort in gebruik. In de jaren veertig stonden in het fort een officierswoning, een kazerne voor Europese en een kazerne voor inlandse soldaten, twee magazijnen, een kruithuis, een wachthuis en een provoost. De bezetting bestond toen uit een 1e luitenant, een 2e luitenant, 44 inlandse infanteristen en zes Europese en 14 inlandse artilleristen. Er woonden ook 31 vrouwen en 21 kinderen in de kazernes. Het fort was bewapend met drie twaalfponders en zes zesponders opgesteld. Het fort werd kort daarna gebruikt als gevangenis en school.
De poort van fort Utrecht werd in 1927-1929 afgebroken. Ook de overige gebouwen zijn met uitzondering van enkele muren, die nu onderdeel zijn van huizen, afgebroken.
