Gedung PT Pelni mulai dibangun pada 1931. Pada saat itu proses pembangunannya memakan waktu selama dua tahun. Kemudian pada 1932, barulah bangunan ini berdiri dengan tegaknya. Pada awalnya, Gedung PT Pelni bernama Stoomvaart Maatschappij Nederland (SMN). Sebelumnya, SMN merupakan sebuah perusahaan pelayaran samudera yang berdiri sejak 1870.

Mengutip dari berbagai sumber,  perusahaan SMN dibangun untuk menyelenggarakan pelayaran dari Belanda menuju Hindia-Belanda, begitu juga sebaliknya. Akan tetapi, ketika masa pendudukan Jepang tempat ini berubah fungsi menjadi Kantor Berita Domei.

Di gedung ini pula, pada Jumat, 17 Agustus 1945 berita Proklamasi Kemerdekaan Indonesia diterima oleh Markonis Yacob. Dengan cepatnya berita tersebut menyebar dan  diterima sampai ke seluruh wilayah Jawa Timur, walaupun pada saat itu Jepang menyensor berita tersebut.