Gedung Negara dibangun pada tahun 1795, waktu itu penguasa tunggal (Gezaghebber) Belanda Dirk Van Hogendorp (1794-1798) beranggapan bahwa tempat kediaman resminya di kota bawah dekat Jembatan Merah kurang sesuai dengna kedudukannya. Ia memilih sebidang lahan di tepi Kalimas untuk membangun sebuah rumah taman yang lebih representatif. Tanah di jalan Pemuda yang dulu bernama Simpang, milik seorang Cina yang mula-mula segan menyerahkannya kepada Van Hogendorp. Namun menurut cerita ia akhirnya berhasil dipaksa secar halus dengan pernyataan bahwa tanah itu akan “disimpan” baginya. Menurut cerita, pemiliknya hanya diberi uang ganti rugi segobang (2.5 sen). Dari kata “disimpan” tadi lahirlah kata SIMPANG. Van Hogendorp membangun gedung itu dengna biaya 14.000 ringgit. Namun ia menikmati tempat kediaman itu hanya sekitar tiga tahun saja.

Selama ia memangku jabatannya, banyak keluhan disampaikan kepada Pemerintah Pusat Hindia Belanda di Batavia (Jakarta), antara lain ia dituduh menyalahgunakan kekuasaan untuk kepentingan pribadi. Itulah sebabnya ketika diadakan resepsi tahun baru pada tanggal 1 Januari 1789, ia ditangkap dan dikirim ke Batavia. Gubernur Jenderal Inggris, Daendels, yang terkenal dengna sebutan Toean Besar Goentoer memperbaiki Gedung Grahadi itu. Ia ingin menjdaikan gedung itu sebagai suatu istana.

Disamping itu, juga dibangun sebuah jembatan di atas Kalimas yang kini mengalir di belakang gedung tersebut. Pada mulanya gedung itu memang menghadap ke Kalimas, sehingga pada sore hari penghuninya sambil minum-minum teh dapat melihat perahu-perahu yang menelusuri kali tersebut. Perahu-perahu itu juga dimanfaatkan sebagai sarana transportasi, mereka datang dan pergi dengna naik perahu menelusuri Kalimas.

Dalam perkembangan berikutnya Gedung yang megah itu dipakai juga untuk tempat bersidang Raad Van Justitie (Pengadilan Tinggi), juga dipakai untuk pesta, resepsi dengna berdansa, dan lain-lain. Pada tahun 1802, gedung Grahadi yang semula menghadap ke Utara, diubah letaknya menjadi menghadap ke Selatan seperti sekarang ini. Di seberangnya ada taman yang bernama Kroesen (Taman Simpang), yang diambil dari nama Residen J.C. Th. Kroesen (1888-1896). Di belakang taman itu ada patung Jokodolok yang berasal dari kerajaan Majapahit yang sekarang juga masih berdiri kokoh. Diantara peninggalan dari zaman Belanda terdapat meja tulis yang kini dipakai oleh Gubernur Jawa Timur di ruang kerjanya. Gubernur Belanda yang terakhir mendiami gedung Grahadi ialah : CH. Hartevelt (1941-1942).

Sejak Indonesia merdeka, Gubernur Jawa Timur pertama yang bertempat tinggal di Grahadi ialah R.T. Soerjo (1946-1948) yang patungnya kini nampak di seberang jalan Gedung tersebut. Sejak Gubernur Samadikoen (1945-1957) sampai sekarang gedung ini dijadikan gedung negara untuk menerima tamu, resepsi serta pertemuan-pertemuan lain, sedangkan Gubernur  sendiri bertempat tinggal di kediaman lain di dalam kota Surabaya.