Berawal pada jaman Hindu-Budha, asal usul nama Desa Penidon berasal dari kata "Nidon" yang berarti Ni (Niat) dan Don (Padudon atau Perebutan) atau jika diterjemahkan maksudnya yaitu niatan untuk merebut kepercayaan warga setempat yaitu Hindu-Budha.

Kedatangan tujuh prajurit dari Mataram melalui bantaran sungai Bengawan Solo yang menyebar di daerah Plumpang di antaranya di Desa Bandungrejo, Desa Klotok, Dusun Lingit, Dusun Kerbut, Desa Penidon, Desa Trepan Kecamatan Babat, dan Desa Sembayat Gresik. Salah satu prajurit tersebut menetap di Desa Penidon dan bertujuan untuk menyebarkan agama Islam yaitu bernama Wongso Dipuro atau Wongso Katiman.

Mbah Wongso Katiman mempunyai niatan kuat untuk mengislamkan warga Nidon. Beliau membangun bangunan kuno berbentuk masjid yang dalam bahasa latah orang kuno disebut Migid atau Semigid. Bangunan tersebut dipakai untuk bersemedi atau beribadah. Berawal dari niatan tersebut, Mbah Wongso Katiman mengubah nama desa Nidon menjadi Penidon. Secara pengucapan nama tersebut hampir sama, hanya saja ditambah kata Pen di depan yang dalam bahasa Jawa Pen berarti niatan yang kuat. Jika diterjemahkan maksudnya yaitu niatan yang kuat untuk mengislamkan warga Desa Penidon, sesuai dengan tujuan utama kedatangan Mbah Wongso Katiman di bumi Penidon.

Pada masa perubahan dari Hindu-Budha menjadi Islam, Desa Penidon terserang wabah penyakit yang mengakibatkan banyak orang meninggal dalam waktu yang cukup singkat. Karena banyaknya korban wabah di Desa Penidon, mbah Wongso Katiman sowan ke Sunan Bejagung untuk meminta bantuan dan do'a agar masyarakat Desa Penidon terlepas dari wabah tersebut. Atas izin Allah wabah penyakit tersebut benar-benar hilang dari Desa Penidon. Sejak saat itu unsur kepercayaan warga Penidon untuk percaya dan menganut ajaran Islam semakin kuat.