Tuban tidak hanya menjadi tempat penting pada masa Kerajaan Majapahit, namun Tuban juga menjadi tempat penting pada masa penyebaran Agama Islam. Hal tersebut dikarenakan Tuban berada di pesisir Utara Jawa yang menjadi pusat Perdagangan arab, dll yang sedang menyebarkan Agama Islam. Hal ini juga berkaitan dengan kisah Sunan Bonang dan Sunan Kalijaga. Sunan Kalijaga adalah putra dari Bupati Tuban VIII Raden Tumenggung Haryo Wilotikto. Sunan Kalijaga dikenal sebagai Brandal Loka Jaya, karena sebelum jadi Wali Sunan Kalijaga adalah brandal (preman) yang suka mencuri hasil kekayaan Kadipaten Tuban. Namun, hasil curian tersebut untuk para Fakir Miskin. Lama-kelamaan, perbuatan tersebut diketahui oleh ayahanda Sunan Kalijaga dan diusir dari Kadipaten Tuban. Dalam pengasingannya, Raden Mas Syahid (Sunan Kalijaga) bertemu dengan Sunan Bonang. Sunan Bonang memiliki Tongkat emas yang membuat Raden Syahid menjadi ingin memiliki tongkat tersebut. Sesaat kemudian, Sunan Kalijaga merebut tongkat emas dan Sunan Bonang jatuh tersungkur. Sunan Bonang menangis dan Sunan Kalijaga merasa iba. Akhirnya Sunan Kalijaga mengembalikan Tongkat Sunan Bonang dan Sunan Kalijaga bertanya bagian mana yang membuat beliau kesakitan. Namun, Sunan Bonang menangis bukan karena kesakitan, tapi beliau menangis karena memutuskan rumput dan beliau berkata bahwa beliau merasa kasihan karena rumput yang tidak bersalah harus mati tercabut karena kesalahan beliau. Sesaat kemudian, beliau menancapkan Tongkat di Pesisir dan menyemburkan air. Tempat tersebut dinamai Sumur Srumbung. Setelah itu, Sunan Bonang menunjukkan Buah Aren yang berwarna emas. Raden Syahidpun tergoda dan memanjat pohon aren tersebut, tapi sebuah aren menimpa kepala beliau dan beliaupun pingsan. Setelah sadar, Raden Syahid diajak Sunan Bonang menuju Sungai di daerah Sekardadi Kecamatan Jenu. Di sana, beliau menjaga tongkat Sunan Bonang yang ditancapkan pada sebuah batu. Anehnya, beliau tertidur selama 2 tahun. setelah sadar, Raden Syahid diberi pakaian dhalang oleh Sunan Bonang dan di Juluki Sunan Kalijaga, maksudnya Kali dalam bahasa Indonesia berarti sungai, dan Jaga dimaksudkan karena sudah menjaga tongkat Sunan Bonang.