In 1632 begon gouverneur-generaal Hendrik Brouwer met de aanleg van een muur van koraalsteen, die Batavia moest beschermen tegen aanvallers. De muur verving de aarden wal die in 1623 aan de oostkant van de stad was aangelegd en de redouten uit 1628 en 1629 die de grotendeels onbebouwde westkant van de stad beschermden. De plaats van de bastions was zo gekozen dat de verdedigers niet alleen aanvallers van buiten konden beschieten, maar bij een oproer de belangrijkste straten onder vuur konden nemen. Om dezelfde reden werd niet alleen een brede buitengracht maar ook een binnen-gracht gegraven. De namen van de bastions werden in 1634 vastgesteld.
Het kasteel beschermde de noordoosthoek van de stad. Vanaf de zuidoostbastion van het kasteel (Robijn) sloot een muur over het kasteelplein aan op eerste bastion van de stadsmuur (Amsterdam). De bastions van de stadsmuur en poorten aan de oostkant van de stad heetten achtereenvolgens: Amsterdam-Middelburg-Delft – Rotterdammer Poort (Pintu Antjol)
Rotterdam, Hoorn, Enkhuizen, Vianen –Gelderland
Catzenellenbogen
Oranje
Nieuwpoort (Pintu Besar) en Hollandia, Het laatste bastion, Grimbergen, beschermde de brug over de Grote Rivier (Kali Besar). Toen in 1640 de muur langs de Kali Besar tussen de bastions Holland en Grimbergen werd opgeleverd, was de versterking van het oostelijke deel van de stad geheel voltooid.
De aanleg van de stadsmuur aan de westkant van de stad verliep langzaam. De stadsgracht werd gegraven, maar het duurde tot 1645 voor het laatste deel van de muur tussen bastion Zeeland en bastion Culemborg was aangelegd. Aan de westkant van de rivier stonden Diestpoort (Pintu Kecil)
bastion Nassau
Zeeland
Utrechse Poort
(West-) Friesland
0verijssel
Groningen
Zeeburg en Culemborg. Het sluitstuk was de drijvende boom waarmee de rivier ‘s nachts werd afgesloten. Aan de overkant stond het kasteel.
De enige aanval op de stad vond plaats toen in oktober 1740 opstandige Chinezen de Diestpoort bestormden. De verdedigers op de wal sloegen de aanval af. Na de opstand werd voor dit bastion een hoornwerk aangelegd.
De muur was al aan het begin van de achttiende eeuw bouwvallig. Na 1750 werden verschillende ontwerpen gemaakt om de militair volkomen verouderde stadsmuur te moderniseren. De uitvoering bleef om financiële reden beperkt tot enkele kleine aanpassingen.
De muur verloor eind 18de eeuw haar laatste betekenis voor de verdediging. De poorten waren niet meer dan een controlepost voor verkeer naar en uit de stad. In 1803 werden de deuren uit de poorten genomen. Tussen 1810 en 1815 werd het grootste deel van de muur afgebroken.
In het noordwestelijke deel van Kota (oud-Batavia) is een klein deel van de muur bewaard gebleven. Het begint met de muur tussen het (verdwenen) bastion Groningen en bastion Zeeburg, daarvandaan loopt de muur door naar het bastion Culemborg. De toren De Uitkijk die omstreeks 1830 op het bastion werd gebouwd, diende voor weerkundige waarnemingen en het melden van binnenkomende schepen.
Van de oostelijke stadsmuur is niets bewaard gebleven. De nog bestaande Oostzijdse Pakhuizen, die tussen 1748 en 1759 op het kasteelplein werden gebouwd, maakten deel uit van de muur tussen het kasteel en bastion Amsterdam.
