Klub ini didirikan pada tahun 2002 oleh PT Samator Group (kini Samator Indo Gas), perusahaan asal Surabaya yang memproduksi gas untuk industri yang kemudian dijadikan nama untuk klub bola voli ini.[3] Pada awal berdirinya, Surabaya Samator bernama Surabaya Flame hingga kemudian berkali-kali berganti nama, seperti Surabaya Flame Samator pada 2003 dan Surabaya Samator pada 2005.[2]
Seiring dengan berjalannya waktu dan juga melihat prestasi tim bola voli ini yang konsisten membuat Polri tertarik ingin bekerja sama dengan Surabaya Samator untuk membentuk dan mengembangkan bola voli di Indonesia mulai dari pembinaan berjenjang hingga berkompetisi di ajang resmi. Pada 2 Juni 2016, manajemen Surabaya Samator menandatangani nota kesepahaman dengan pihak Polri yang dalam hal ini diwakili oleh Kepala Korlantas Polri dan setelah adanya kerja sama tersebut nama Surabaya Samator resmi berubah menjadi Surabaya Bhayangkara Samator.[3]
Mulai akhir 2022, klub ini resmi bernama Surabaya BIN Samator setelah menggandeng pihak Badan Intelijen Negara menjelang Livoli Divisi Utama 2022.[4][5] Ini adalah klub voli kedua yang dikerjasamakan oleh BIN setelah klub voli putri BIN O2C Subang pada Livoli Divisi I 2022. Sebelumnya, Polri menghentikan kerja sama dengan klub ini dan membentuk klub bernama Jakarta Bhayangkara Presisi pada September 2022.[6][7]
Surabaya BIN Samator merupakan tim tersukses di kompetisi tertinggi bola voli putra Proliga sejak kompetisi ini diperkenalkan pada tahun 2002 lalu. Total 7 gelar juara berhasil diraih oleh tim ini.[12] Di Livoli Divisi Utama, tim ini juga menjadi tim tersukses dengan 8 gelar juara yang diraih.[13]