Desa Ngrejeng berasal dari kata ngences/ngejeng yang berawal dari cerita atau dongeng orang terdahulu. Cerita tentung asal muasal desa Ngrejeng yang paling terkenal adalah pada pertengahan abad 18 paska terjadinya perang pajang yaitu perang besar di tanah Jawa belanda pada masa kesultanan Raja Batu. di utuslah salah satu perwira untuk menjaga bom sebagai senjata perang pada saat itu setelah selesai menjalankan tugas nya kemudian beliau merantau kesebuah dataran tinggi yang berada di sebelah barat daya kota Tuban.Sesampainya di datran tinggi beliau mulai untuk babat hutan atau dalam bahasa jawa Bubak Bumi. Dalam membabat hutan beliau membabat secara diagonal / tidak lurus atau dalam bahasa jawa disebut Ngences/Ngejeng, Konon asal muasal nama Ngrejeng berasal dari kata ngejeng yang berubah pengucapannya menjadi Ngrejeng.Setelah berhasil membabat hutan kemudian beliau membuat sumur untuk memenuhi kebutuhan hidup sehari-hari dan sumur tersebut dinamai Sumur Mastoko.