Namun demikian, sejarawan mengakui sangat kesulitan untuk merekonstruksi masa pengaruh Hindu-Budha di Madura ini karena kelangkaan sumber sejarah. Hanya ada beberapa candi baik di Pamekasan dan Sumenep sebagai bukti bahwa agama Hindu-Budha pernah dianut masyarakat Madura.
De Graaf mengakui, untuk merekonstruksi sejarah Jawa, termasuk Madura, terpaksa menggali dari sumber yang keruh. Diperkirakan pengaruh Hindu-Budha yaitu sejak abad ke 9, sejak berkembangnya cerita Raden Segoro, sampai sekitar abad ke 15, yakni setelah mulai berkembangnya masyarakat mengenal Islam lalu memeluknya.
Pengaruh kuat Hindu-Budha juga diperkuat dengan adanya catatan bahwa di abad-abad itu secara berturut-turut Madura dibawah pengaruh Kediri (1050-1222), Singosari (1222-1292) dan Majapahit (1294-1572), yang kesemuanya beragama Hindu dan Budha. Sebab itu, istilah “Madura” tidak jarang disebut-sebut dalam tulisan-tulisan orang Hindu sebagaimana dalam Pararaton yang menyebut istilah “Madura Wetan”, Madura bagian timur, yakni Sumenep.
Sampai di sini agama primitif orang Madura bisa dipastikan tidak jauh berbeda dengan masyarakat Jawa pra Islam, yaitu Hindu-Budha. Adapun agama selain itu adalah agama baru yang datang kemudian, termasuk Islam dan Kristen. Selanjutnya akan dijabarkan proses Islamisasi Madura.
Islamisasi Madura
Proses Islamisasi Madura boleh dibilang suatu proyek dakwah yang menuai hasil yang luar biasa. Proyek dakwah ini sebenarnya adalah kelanjutan dari mega proyek Islamisasi Nusantara yang sangat massif di antara abad ke-7 hingga abad ke-15 melalui tangan-tangan ikhlas para juru dakwah yang di Jawa dikenal dengan Wali Songo. Madura juga menjadi bagian agenda mega proyek ini.
