Pada awal mulanya, balai kota pertama di Batavia dibangun pada tahun 1620 di tepi timur Kali Besar. Bangunan ini hanya bertahan selama enam tahun sebelum akhirnya dibongkar demi menghadapi serangan dari pasukan Sultan Agung pada tahun 1626.^[1] Sebagai gantinya, dibangunlah kembali balai kota tersebut atas perintah Gubernur-Jenderal Jan Pieterszoon Coen pada tahun 1627. Lokasinya berada di daerah Nieuwe Markt (sekarang Taman Fatahillah).^[2] Menurut catatan sejarah, balai kota kedua ini hanya bertingkat satu dan pembangunan tingkat kedua dilakukan kemudian. Tahun 1648 kondisi balai kota sangat buruk. Tanah di kota Batavia yang sangat labil dan beratnya bangunan ini menyebabkan perlahan-lahan turun dari permukaan tanah.

Akhirnya pada tahun 1707, atas perintah Gubernur-Jenderal Joan van Hoorn, bangunan ini dibongkar dan dibangun ulang dengan menggunakan pondasi yang sama. Peresmian Balai kota ketiga dilakukan oleh Gubernur-Jenderal Abraham van Riebeeck pada tanggal 10 Juli 1710, dua tahun sebelum bangunan ini selesai secara keseluruhan.^[2] Selama dua abad, balai kota Batavia ini digunakan sebagai kantor administrasi kota Batavia. Selain itu juga digunakan sebagai tempat College van Schepenen (Dewan Kotapraja) dan Raad van Justitie (Dewan Pengadilan). Awalnya sidang Dewan Pengadilan dilakukan di dalam Kastil Batavia. Namun dipindahkan ke sayap timur balai kota dan kemudian dipindahkan ke gedung pengadilan yang baru pada tahun 1870.^[2]