Kantor Pemerintahan Surabaya sebelumnya berada di Kembang Jepun hingga tahun 1930. Gedung kantornya tepat berada di mulut Jembatan Merah. Sehingga, kawasan Kembang Jepun dulu, selain sebagai pusat pemerintahan Kota Surabaya, merupakan kawasan bisnis utama pada waktu itu. Seiring perjalanan waktu, kepadatan Kembang Jepun tak bisa dihindari lagi. Bangunan kantor gubernur dari segi arsitektur tidak begitu anggun, didepan banyak kendaraan diparkir sekitar jalan itu, harus dipindahkan ke daerah yang belum padat. Gedung baru mulai dibangun bulan Mei 1929 oleh NV Nederlandsche Aanneming Maatschappij (Nedam), dan selesai bulan Agustus 1931.
Setelah itu mulai digunakan 10 Desember 1931 sebagai Kantor Gubernur, Kantor Residen, dan Kantor Kepolisian Karesidenan. Arsiteknya adalah Ir. W. Lemei, HA. Breuning dan WB Carmiggelt dari Landsgebouwdienst atau Djawatan Gedong-Gedong Negara di Surabaya. Gedung ini merupakan karya arsitektur terbesar dari Ir W Lemei. Gedung dilokasi saat ini berdiri diatas sebidang tanah seluas 11.612 m², bangunan utama terdiri atas dua lantai dengan luas bangunan 7.865 m². Ciri khas bangunan ini berwarna putih seluruhnya dengan menara jam yang memiliki ornamen kubah kecil keemasan di puncaknya.
Gedung ini merupakan simbol dari modernisasi kota yang menjadi pusat pemerintahan dan ekonomi di Jawa Timur. Konon, gedung ini merupakan salah satu simbol pembangunan gedung-gedung berarsitektur modern di Surabaya. Banyak orang mengatakan bahwa ide gedung ini mirip dengan bangunan gedung balai kota Hilversum Belanda, hasil karya arsitek Belanda terkenal Ir. W. Dudok.
Tata masa segi empat, portico adalah teras yang mengarah ke pintu masuk bangunan, atau diperpanjang sebagai barisan tiang, dengan struktur atap di atas jalan setapak, didukung oleh kolom atau tertutup oleh dinding. Ide ini banyak digunakan di Yunani Kuno yang telah mempengaruhi banyak budaya, termasuk sebagian besar budaya Barat. Terdapat gang yang mengelilingi taman dalam, sangat sesuai dengan iklim tropis Surabaya. Pada masa pendudukan Jepang, gedung ini pernah diambil alih dan difungsikan sebagai Kantor Syuuchokan (Karesidenan) karena jabatan gubernur dalam tata pemerintahan Jepang tidak dikenal. Setelah Indonesia merdeka, gedung ini difungsikan kembali sebagai Kantor Gubernur, Kantor Residen, dan Kantor Kepolisian Karesidenan. Akan tetapi, dalam perkembangannya, Kantor Kepolisian Karesidenan selanjutnya menempati gedung tersendiri bekas Hoofdbureau van Politie di Paradestraat atau Jalan Sikatan. Sedangkan, Kantor Karesidenan sebagai Kantor Pembantu Pembantu Kepala Daerah Provinsi Jawa Timur dipindahkan ke Jalan Raya Gubeng. Seiring kebutuhan akan sumber daya manusia, penambahan jumlah pegawai di lingkungan Kantor Gubernur pun tidak bisa dihindari. Konsekuensinya, perlu penambahan ruangan untuk memenuhi ruangan kantor yang harus melebihi kapasitas di atas 300 orang. Akhirnya, dibangun kantor baru di belakang gedung lama pada 10 Oktober 1981 dengan mensinergikan gaya arsitektur bangunan lama yang berada di depannya.
Di gedung Kantor Gubernur Jawa Timur ini Presiden Soekarno berunding dengan Jenderal Hawthorn untuk mendamaikan pertempuran Oktober 1945, dan bahwa Gubernur Soerjo pada 9 November 1945 jam 23.00 memutuskan menolak ultimatum Jenderal Mansergh untuk menyerah tanpa syarat sehingga terjadilah pertempuran 10 November 1945.
