Surabaya sebagai Resort Gemeente (Haminte) secara resmi mulai berdiri pada tanggal 1 April 1906. Sebelumnya Surabaya merupakan bagian dari keresidenan Pemerintah Haminte yang dijalankan oleh Dewan Haminte yang diketuai oleh asisten residen sebagai Kepala Daerah.
Tahun 1916 diangkat Wali Kota Surabaya pertama, A. Meyroos, yang bertugas sampai tahun 1921. Baru setelah Wali Kota yang kedua, G.J. Dijkerman, terpilih, rencana membangun gedung Balai Kota diwujudkan.
Gedung utama Balai Kota di Taman Surya di daerah Ketabang mulai dibangun pada tahun 1923 dan mulai ditempati pada tahun 1927. Arsiteknya ialah C. Citroen dan pelaksanaannya H.V. Hollandsche Beton Mij. Biaya seluruhnya, termasuk perlengkapan dan lain-lainnya, menghabiskan dana sekitar 1.000 gulden.
Ukuran gedung utama: panjang 102 m dan lebar 19 m. Konstruksinya terdiri dari tiang-tiang pancang beton bertulang yang ditanam, sedangkan dinding-dindingnya diisi dengan bata dan semen. Atapnya terbuat dari rangka besi dan ditutup dengan sirap. Belakangan, atap ini kemudian diganti dengan genting.