Madrasah Ibtidaiyah Raudlatul Mustasyidin didirikan di tengah-tengah kegelisahan sekelompok masyarakat yang melihat banyak anak-anak Madura yang tidak bisa mengenyam pendidikan sekolah dasar karena terbentur oleh birokrasi yang njelimet dan kondisi ekonomi masyarakat yang tidak bisa menjangkau mahalnya biaya pendidikan ketika itu. Kegelisahan itu semakin menjadi-jadi karena jumlah anak-anak yang tidak bisa mengenyam sekolah dasar terus meningkat signifikan dan masyarakat Madura terancam akan menjadi masyarakat terpinggirkan Karena tidak bisa menikmati kursi sekolah.
Sehingga berdasarkan kondisi seperti itulah keinginan untuk mendirikann lembaga pendidikan dasar yang bisa menampung anak-anak yang terancam masa depannya semakin menguat, dengan hanya bermodalkan kemauan dan semangat perjuangan yang membara-bara tanpa ada sumber dana sepersenpun madrasah Ibtidaiyah Raudlatul Mustarsyidin lahir.
Tidak sedikit masyarakat yang mencela dan memandang sebelah mata keberadaan madrasah Raudlatul Mustarsyidin yang pada awal pendiriannya memang hanya menempati sebuah gubuk reot yang tidak refresentatif dan jauh dari kata layak untuk ditempati sebuah lembaga pendidikan yang notabenenya adalah tempat untuk mencetak generasi masa depan bangsa Indonesia.
Keberlangsungan perjalanan panjang madrasah Ibtidaiyah Raudlatul Mustarsyidin penuh dengan liku dan kerikil tajam yang datang silih berganti, keberlangsungan proses pendidikan yang berjalan dengan memakai bangunan dengan tanah yang masih mengontrak terancam berhenti karena dipermasalahkan tentang izin operasional bangunan oleh pemerintah di tingkat desa dan pemilik tanah dan memberikan deadline waktu yang membuat pengurus yayasan dan dewan guru ketika itu kelabakan untuk menyelamatkan proses pendidikan yang sedang berlangsung. banyak kalangan yang sudah memprediksi bahwa perjalanan Madrasah Ibtidaiyah Raudlatul Mustarsyidin akan segera tamat. Namun pada akhirnya pada tanggal 5 januari 2005 Madrasah Ibtidaiyah Raudlatul Mustarsyidin kembali mendapatkan tempat menumpang untuk sementara waktu di tanah H. Ali Murtadla sampai 22 Juli 2006 dan di dalam masa-masa sulit itulah sebagian besar masyarakat Madura berjuang dan bergerak untuk bergotong royong dan saling bahu membahu untuk melakukan penggalangan dana di dalam usaha untuk membeli tanah dan mendirikan gedung Madrasah yang permanen.
Hasil kerja keras dan pantang putus asa itu, hari ini kita bisa melihat dan merasakan megahnya bangunan gedung Madrasah Ibtidaiyah Raudlatul Mustarsyidin seperti saat ini.