Islam dipercayai telah mula bertapak di Sarawak selewat-lewatnya pada kurun ke-16 Masehi melalui pengaruh Kesultanan Melayu Brunei Darussalam. Pertabalan Sultan Tengah sebagai Sultan Sarawak Darul Hana (dengan gelaran Sultan Ibrahim Ali Omar Shah) pada 99 Masehi dianggap sebagai detik rasmi bertapaknya Islam di Sarawak. Para Sharif berketurunan Arab telah mendapat penghormatan dan kepercayaan untuk mentadbir urusan umat Islam bagi pihak pemerintah Brunei. Setelah pentadbiran Sarawak diambil alih oleh Brooke pada 1841, semua urusan umat islam telah dikendalikan oleh Mahkamah Datu-Datu (Datu's Court).
Dalam masa yang sama, Majlis Shuyukh Al-Islam yang dipelopori oleh empat (4) orang tokoh yang dipelopori oleh empat (4) orang tokoh, iaitu Mufti Abang Haji Nawawi, Imam Abang Haji Bahauddin, Abang Haji Julaihi dan Haji Salleh Arif telah ditubuhkan bagi mengimbangi peranan mahkamah tersebut. Setelah Sarawak diserahkan kepada koloni British pada 1946, Kerajaan British telah menggubal Ordinan Mailis Islam (Pemerbadanan), Bab 105 pada 17 Disember 1954 dengan hasrat untuk menubuhkan satu badan bagi menjaga hal ehwal agama Islam dalam negeri. Akhirnya pada 1 Mei 1955, Majlis Islam Sarawak (MIS) yang pertama telah ditubuhkan atas nama Majlis Islam dan Adat Istiadat Melayu Sarawak.
Datu Abang Haji Openg bin Abang Sapi'ee telah dilantik sebagai Yang Dipertua MIS yang pertama dengan anggota-anggotanya terdiri daripada Haji Abang Bahauddin bin Haji Taha, Haji Busrah bin Osman, Mohamed Yakub, Haji Bolhassan bin Haji Daud, Che Jol bin Abdul Karian, Haji Seruji bin Ali, Abang Morni bin Abang Haji Latif dan Datu Hakim Abang Haji Mohideen (Ex-Officio). Setiausaha Pertama ialah Abang Daim bin Haji Abdul Rahim. Pada awal penubuhannya, majlis ini merupakan sebuah jabatan kerajaan di bawah kerajaan British. Jumlah kakitangannya ketika itu amat sedikit terdiri daripada lima (5) orang sahaja iaitu seorang Presiden, Datu Hakim (Magistrate), seorang kerani kanan (Setiausaha), seorang kerani dan seorang budak pejabat.
Pada tahun 1975, jumlah kakitangan MIS telah bertambah kepada 22 orang. Melalui penstrukturan terkini pada tahun 2019, Pejabat Majlis Islam Sarawak telah mempunyai sebanyak 91 jawatan. Bagi membantu MIS menjalankan fungsinya, empat (4) buah Lembaga telah diwujudkan di bawah struktur MIS iaitu Lembaga Fatwa, Lembaga Baitulmal dan Wakaf. Lembaga Masjid-Masjid dan Lembaga Hal-Ehwal Islam dan Adat Melayu. Ordinan Majlis Islam (Pemerbadanan), 1954 telah mengalami beberapa pindaan bagi memperkasakan lagi fungsi MIS dengan penubuhan beberapa badan Islam iaitu Tabung Zakat dan Fitrah (1966), Mahkamah Syariah (1978), Tabung Baitulmal Sarawak (1985) dan Jabatan Agama Islam Sarawak (1990).
Di samping itu, beberapa agensi lain juga telah diwujudkan iaitu Jabatan Kehakiman Syariah Sarawak (1990), Jabatan Mufti Negeri Sarawak (1997), Biro Perkhidmatan Pendidikan (2007) dan Pusat Penerangan Islam (2008).