Sejarah Desa Randuwatang tidak terlepas dari legenda masyarakat setempat di Kabupaten Jombang. Menurut cerita nenek moyang terdahulu yang diturunkan kepada tokoh masyarakat dan para pini sepuh kepada anak-anak cucu, warga masyarakat adalah sebagai berikut :
Konon ada seorang tokoh yang bernama Kebo Kicak, adalah seorang yang mempunyai kesaktian luar biasa dengan wujud kepala kerbau dan berbadan manusia. Dia berwatak jahat dan sering merugikan kehidupan masyarakat serta sering membuat onar. Sedangkan tokoh yang lain bernama Surontanu, beliau adalah seorang tokoh yang berjiwa besar suka menolong orang dan beliau juga mempunyai kesaktian yang tidak kalah dengan Kebo Kicak. Oleh sebab itu Kebo Kicak tidak suka dengan apa yang telah dilakukan oleh Surontanu, sehingga kebo kica berusaha membunuh Surontanu. Tak kenal siang dan malam Kebo Kicak selalu mencari informasi tentang dimana keberadaan Surontanu.
Pada suatu hari Kebo Kicak mendapat informasi bahwa Surontanu berada di desa kandang sapi ditempat seorang janda miskin yang perlu untuk ditolong, setelah mendengar kabar itu dengan spontan Kebo Kicak berangkat untuk mencarinya, setelah sampai ditempat yang dimaksud surontanu bersembunyi di kandang sapi milik tuan rumah. Sehingga Kebo Kicak kehilangan jejak, setelah Surontanu selamat dari kehajatan Kebo Kicak maka desa tersebut dinamakan desa Kandang sapi. Kemudian Surontanu meninggalkan desa tersebut menuju desa Jati Duwur Kecamatan Kesamben Kabupaten Jombang, yang pada waktu itu masih berupa hutan belantara yang rimbun dan berbukit, yang sebagian besar ditumbuhi pohon jati. Namun diantara pohon jati tersebut ada pohon randu yang kecil dan panjang.
Pada hari berikutnya Kebo Kicak mendengar kabar bahwa Surontanu berada di hutan tersebut, sehingga dengan cepatnya Kebo Kicak memburunya karena Surontanu merasa jiwanya terancam maka dia menyelamatkan diri dengan cara memenjat pohon jati yang tinggi (duwur) sehingga Kebo Kicak tidak mengetahuinya. Pada akhirnya Surontanu selamat sehingga sampai sekarang hutan tersebut dinamakan desa Jati Duwur. Setelah Kebo Kicak meninggalkan hutan tersebut surontanu memotong jati tersebut untuk dijadikan perahu sedangkan watangnya (tongkat perahu) diambilkan dari pohon randu. Perahu tersebut digunakan untuk menyeberangi sungai brantas, sesampainya diseberang sungai brantas disebelah utara yang akhirnya desa tempat menambatkan perahu dengan watang kayu randu tersebut dinamakan Randuwatang.