Runtuhnya rezim Orde Baru yang otoriter dan penerapan otonomi daerah yang tidak lagi sentralistik telah menandai adanya perubahan politik yang sangat radikal di republik ini. Perubahan ini tentunya juga berimbas pada mekanisme kepemimpinan di tingkat lokal seperti yang terjadi di masyarakat Madura. Faktor perubahan rezim ini juga ditambah dengan dibangunnya jembatan Suramadu sehingga masyarakat Madura semakin terbuka melakukan akses dengan dunia luar baik secara ekonomi maupun sosial-budaya. Pada masa Orde Baru, pengalaman politik masyarakat Madura sangat bergantung pada Kiai sebagai akibat dari otoritarianisme penguasa. Di masa kejayaan Golkar sebagai the ruling party, may­oritas kiai di Madura mengambil jarak dengan kekuasaan dan memban­gun orientasi sosial keagamaan sepenuhnya pada masyarakat. Setelah perubahan rezim, para kiai yang sebelumnya menjadi tokoh non-formal menjelma menjadi penguasa (Bupati). Ironisnya, setelah lima tahun rezim kiai memimpin tampuk pemerintahan di sebagian besar kabupaten di Madura, hampir tidak ada perbedaan yang signi­fikan dalam menciptakan perubahan kesejahteraan rakyat.