Surabaya secara resmi berdiri pada tahun 1293. Tanggal peristiwa yang diambil adalah kemenangan Raden Wijaya, Raja pertama Mojopahit melawan pasukan Cina.Peranan Surabaya sebagai kota pelabuhan sangat penting sejak lama. Saat itu sungai Kalimas merupakan sungai yang dipenuhi perahu-perahu yang berlayar menuju pelosok Surabaya.
Bukti sejarah menunjukkan bahwa Surabaya sudah ada jauh sebelum zaman kolonial, seperti yang tercantum dalam prasasti Trowulan I berangka 1358 M. Dalam prasasti tersebut terungkap bahwa Surabaya (Churabhaya) masih berupa desa ditepian sungai Berantas sebagai salah satu tempat penyeberangan penting sepanjang sungai tersebut.
Surabaya (Churabhaya) juga tercantum dalam pujasastra Negara Kertagama yang ditulis oleh Mpu Prapanca tentang perjalanan pesiar baginda Hayam Wuruk pada tahun 1385 M dalam pupuh XVII. Walaupun bukti tertulis tertua mencantumkan nama Surabaya berangka tahun 1358 M Prasasti Trowulan) dan 1365 M (Negara Kertagama), para ahli menduga bahwa Surabaya sudah ada sebelum tahun-tahun tersebut.
Menurut hipotesis Von Faber, Surabaya didirikan tahun 1275 M oleh Raja Kertanegara sebagai tempat pemukiman baru bagi prajuritnya yang berhasil menumpas pemberontakan Kemuruhan tahun 1270 M. Hipotesis yang lain mengatakan bahwa Surabaya dulu bernama Ujung Galuh.
Versi lain mengatakan bahwa nama Surabaya berasal dari cerita tentang perkelahian hidup dan mati Adipati Jayengrono dan Sawunggaling. Konon setelah mengalahkan tentara Tartar, Raden Wijaya mendirikan sebuah Keraton di Ujung Galuh dan menempatkan Adipati Jayengrono
Kata “ SURABAYA “ juga sering diartikan secara filosofis sebagai lambang perjuangan antara darat dan air, antara tanah dan air. Selain itu dari kata Surabaya juga muncul mitos pertempuran antara ikan Suro (Sura) dan Boyo (Baya atau Buaya), yang menimbulkan dugaan bahwa nama Surabaya muncul setelah terjadinya peperangan antara ikan Sura dan Buaya (Baya)
Agar tidak menimbulkan kesimpang-siuran dalam masyarakat maka Walikotamdya Kepala Daerah Tingkat II Surabaya, dijabat oleh Bapak Soeparno, mengeluarkan Surat Keputusan No. 64/WK/75 tentang penetapan hari jadi kota Surabaya. Surat Keputusan tersebut menetapkan tanggal 31 Mei 1293 sebagai tanggal hari jadi kota Surabaya. Tanggal tersebut ditetapkan atas kesepakatan sekelompok sejarahwan yang dibentuk oleh Pemerintah Kota bahwa nama Surabaya berasal dari kata “Sura ing Bhaya” yang berarti “ Keberanian menghadapi bahaya “ diambil dari babak dikalahkannya pasukan Mongol oleh pasukan Jawa pimpinan Raden Wijaya pada tanggal 31 Mei 1293.
Agar tidak menimbulkan kesimpang-siuran dalam masyarakat maka Walikotamdya Kepala Daerah Tingkat II Surabaya, dijabat oleh Bapak Soeparno, mengeluarkan Surat Keputusan No. 64/WK/75 tentang penetapan hari jadi kota Surabaya. Surat Keputusan tersebut menetapkan tanggal 31 Mei 1293 sebagai tanggal hari jadi kota Surabaya. Tanggal tersebut ditetapkan atas kesepakatan sekelompok sejarahwan yang dibentuk oleh Pemerintah Kota bahwa nama Surabaya berasal dari kata “Sura ing Bhaya” yang berarti “ Keberanian menghadapi bahaya “ diambil dari babak dikalahkannya pasukan Mongol oleh pasukan Jawa pimpinan Raden Wijaya pada tanggal 31 Mei 1293.
Masih banyak cerita lain tentang makna dan semangat Surabaya. Semuanya mengilhami pembuatan lambang-lambang Kota Surabaya. Lambang kota Surabaya yang berlaku sampai saat ini ditetapkan oleh DPDRS kota besar Surabaya yang keputusan No. 34/DPRS tanggal 19 Juni 1955 diperkuat dengan Keputusan Presiden R.I No. 193 tahun 1955 tanggal 14 Desember 1956.