Cerita ini bermula ketika pada zaman dahulu tepatnya pada tahun 840 M terdapat seseorang yang bertapa dan meminta petunjuk di daerah ini, orang tersebut bernama Ki Jalak Ijo/Kyai Jalak Ijo (Kumbang Wijoyo Kusumo) yang diutus oleh kerajaan, karena dahulu di daerah selatan Tuban berdiri sebuah kerajaan kecil bernama Kerajaan Gumenggeng (tempat sekarang disebut Desa Gumeng, Kecamatan Rengel). Kerajaan tersebut di pimpin oleh seorang raja bernama Raden Arya Bangah putra dari Kyai Gedhe Lele Lontang. Karena letak kerajaan ini yang di kelilingi pegunungan kapur, membuat kerajaan ini sering dilanda kekeringan. Suatu ketika kerajaan ini dilanda kekeringan/kemarau panjang dan paceklik, sehingga banyak rakyatnya yang gagal panen dan kekurangan air, sehingga banyak rakyat kerajaan gumenggeng yang kelaparan dan kekeringan. Hal ini membuat Raja Arya Bangah harus bertindak, kemudia ia memutuskan untuk bersemedi/meditasi di puncak bukit Nglai (sekarang bernama puncak Ngandong, Kecamatan Grabagan, Kabupaten Tuban) untuk meminta petunjuk dari dewa. Kemudian ia mendapatkan petunjuk dalam mimpinya bahwa untuk mengatasi kekeringan yang melanda kerajaan, harus ada yang berani bertapa di daerah sekitar kerajaan, dimana daerah tersebut di jaga oleh para jin dan menjadi tempat kerajaan jin, sehingga banyak orang yang takut mendekati daerah tersebut karena siapapun yang berani datang ke daerah tersebut tidak akan pernah bisa kembali dan hilang selamanya. Sang raja pun mengadakan sebuah sayembara bagi siapapun yang berani untuk bertapa di daerah tersebut, hingga kemudian munculah Ki Jalak Ijo yang bersedia untuk melakukan tapa brata di daerah tersebut. Kemudian Ki Jalak Ijo diperintahkan oleh kerajaan untuk bertapa di daerah tersebut dengan di dampingi oleh senopati dan pengawal Kerajaan Gumenggeng. Ketika hendak mencapai daerah tersebut, jalan atau medan yang dilewati cukup sulit, menanjak dan terjal karena terdiri dari bebatuan atau dalam bahasa jawa disebut ngrengkel-ngrenkel sehingga untuk selanjutnya daerah tersebut diberinama daerah Rengel dari kata Rengkel-ngerengkel (menanjak dan terjal), hingga saat ini daerah tersebut diberi nama kecamatan Rengel. Kemudian sesampainnya di sana Ki Jalak Ijo bertemu dengan seorang wanita bernama Dewi Laras yang baru selesai melahirkan dan membutuhkan minum, tetapi di daerah tersebut tidak ada air, kemudian Ki Jalak Ijo berniat untuk mencarikan air, hingga Ki Jalak Ijo menemukan sebuah celah/goa (rong) di sekitar daerah tersebut sehingga goa itu diberinama Goa Ngerong karena berasal dari kata “Rong/ngerong” yang berarti celah/ceruk. Kemudian Ki Jalak Ijo meyakini bahwa disinilah tempatnya untuk melakukan tapa-brata sambil menancapkan tongkatnya di celah bebatuan, hal ini untuk meminta petunjuk dan wasilah kepada Tuhan Yang Maha Kuasa. Setelah melakukan tapa brata di daerah tersebut Ki Jalak Ijo mendapatkan petunjuk dan kemudian ia mencabut tongkatnnya tersebut (sebagaian versi cerita mengatakan bahwa Ki Jalak Ijo mencukil sebuah batu dengan tongkatnnya). Namun sebelum meninggalkan tempat tersebut Ki Jalak Ijo berpesan pada Senopati dan pengawal kerajaan untuk tidak menoleh kebelakang saat mereka meninggalkan tempat tersebut apapun yang terjadi. Kemudian mereka bersama-sama meninggalkan temapt tersebut, namun saat hendak pergi terdengar suara dan terlihat bayangan seorang gadis cantik jelita memanggil-manggil mereka, tetapi senopati dan pengawal kerajaan penasaran dan lalai dengan pesan Ki Jalak Ijo karena tergoda oleh gadis tersebut, hingga senopati dan pengawal menoleh kebelakang, namun gadis yang cantik jelita tersebut hilang dan berubah menjadi ikan raksasa tanpa daging (ikan truno lele) ternyata gadis tersebut adalah jilmaan dari penunggu daerah tersebut yang diyakini juga sebagai putri Goa Ngerong, lalu senopati dan pengawal dikutuk dan kemudian hilang dan berubah wujud menjadi Kura-kura (bulus) dan ikan lele, yang menjadi penunggu dan penghuni Goa Ngerong. Bersamaan dengan hal tersebut dari celah bekas tongkat Ki Jalak Ijo muncullah sumber air yang sangat deras dan akhirnya membentuk aliran sungai, sehingga dibawah Goa Ngerong terdapat aliran sungai panjang yang mengalir membelah Desa Rengel, dari aliran sungai tersebut juga muncul ikan-ikan yang sangat banyak dan sampai sekarang masih menjadi penghuni air sungai Goa Ngerong bersama dengan kura-kura (bulus), ikan lele raksasa, dan ikan tulang tanpa daging yang bernama ikan truno lele yang dipercaya hanya muncul pada waktu-waktu tertentu dan hanya bisa dipanggil oleh Juru Kunci penjaga Goa Ngerong. Melihat sang senopati dan pengawal kerajaan berubah menjadi kura-kura(bulus) dan ikan lele, membuat Ki Jalak Ijo tidak bisa bertindak apapun karena kutukan tersebut berasal dari Tuhan, kutukan tersebut disebabkan karena telah melanggar pantangan/pesan Ki Jala Ijo untuk tidak menoleh ke belakang apapun yang terjadi, namun mereka melanggar pesan Ki Jala Ijo sehingga mereka dikutuk menjadi jelmaan hewan yang hingga kini menjadi penunggu Goa Ngerong bersama ikan tulang tanpa daging yang merupakan jelmaan puteri Goa Ngerong. Berkat air yang memancar dan bersumber dari Goa Ngerong karena wasilah yang diperoleh dari tapa-brata yang dilakukan oleh Ki Jala Ijo membuat seluruh rakyat di sekitar daerah tersebut dan seluruh rakyat Kerajaan Gumenggeng menjadi tidak mengalami kekeringan dan kehausan lagi dan dapat menolong orang-orang yang kehausan serta mengembalikan kesuburan dan meningkatkan hasil panen masyarakat sekitar dan Kerajaan Gumenggeng karena berkah dari aliran suang Goa Ngerong.

Kemudian Ki Jalak Ijo berpesan kepada seluruh masyarakat, baik masyarakat setempat maupun masyarakat yang berasal dari luar daerah/kerajaan jika mendatangi tempat tersebut agar tidak mengambil ikan yang hidup di Goa Ngerong, karena jika nekat melanggar pantangan/larangan tersebut akan berakibat kemalangan, kesialan dan bahkan orang yang mengambil ikan tersebut baik untuk dimakan atau apapun hal lain akan kehilangan nyawanya dan berakhir tragis. Larangan tersebut terus berkembang dan sampai sekarang masih diyakini kebenarannya sehingga menjadi sebuah mitos yang melegenda bahwa tidak ada satupun yang boleh mengambil ikan, kura-kura (bulus) atau hewan lain yang hidup di Goa Ngerong. Mitos ini pun akhirnya berkembang menjadi segala apapun yang ada di lokasi wisata Goa Ngerong seperti batu, air atau tumbuhan dan lain-lain, tidak boleh diambil atau dibawa pulang, dan jika dilanggar akan berakibat kesialan dan kemalangan yang tidak akan berakhir sampai orang yang mengambil sesuatu tersebut, mengembalikan sesuatu itu ke tempatnya semula di lokasi Goa Ngerong. Sampai sekarang mitos/larangan/pantangan yang ada di Goa Ngerong masih di yakini oleh masyarakat dan pengunjung dan menjadi bagian tradisi dan kebudayaan yang tak terpisahkan dari Goa Ngerong, hal ini memberi dampak positif tidak hanya dari segi kebudayaan dan tradisi, tetapi juga dari segi lingkungan dan ekosisitem yang masih terjaga dan alami di lokasi wisata Goa Ngerong, hewan-hewan penghuni goa ngerong masih banyak dijumpai mulai dari jutaan kelelawar yang menggantung di langit-langit goa, jutaan ikan yang hidup di aliran air Goa Ngerong, bulus, kera dan masih banyak lagi, terjaga dari kepunahan karena mitos yang berkembang. Aliran air Goa Ngerong sampai sekarang juga masih dimanfaatkan oleh masyarakat Desa Rengel untuk berbagai keperluan seperti untuk pariwisata, kebutuhan hidup dan bahkan dimanfaatkan sebagai sarana pengairan irigasi ribuah hektar lahan persawahan di Desa Rengel.

Masyarakat sampai sekarang juga mempertahankan tradisi yaitu dengan mengadakan tradisi “Manganan” atau sedekah bumi, yang diadakan setiap bulan besar minggu kliwon, diperingati dengan menyembelih kambing, sapi atau ayam, serta menggelar pagelaran wayang semalam suntuk. Selain itu masyarakat juga rutin berziarah ke makam/petilasan Ki Jalak Ijo yang ada di dalam area wisata Goa Ngerong setiap jum’at legi. Berbagai tradisi dan mitos tersebut tetap hidup sampai hari ini, dan menambah daya tarik wisata Goa Ngerong