Jejak keislaman di Bali bisa setidaknya dirunut dari hubungan diplomatik yang baik antara Majapahit sebagai negara penguasa dengan Bali sebagai negara vasal (negara yang dikuasai). 

Pada 1380-an, Hayam Wuruk sedang mengadakan konferensi di kerajaannya, sehingga ia mengundang negara-negara koloni Majapahit dari seluruh wilayah Nusantara. Kerajaan Gelgel di Bali sebagai negara taklukan pun turut diundang, yang diwakili oleh Dalem Ketut Ngalesir (1380- 1460). 

Kerajaan Gelgel adalah pecahan dari Kerajaan Samprangan yang dikuasai kakak tertua Dalem Ketut Ngalesir.

Setelah menghadiri pertemuan tersebut, perjalanan pulang raja pertama Kerajaan Gelgel tersebut diantar oleh 40 prajurit Majapahit yang beragama Islam. Prajurit Majapahit tersebut kemudian menetap dan membangun masyarakat sendiri di Gelgel, yang kemudian dikenal dengan Kampung Gelgel.

Informasi di atas diperkuat sumber lisan yang dikumpulkan dari cerita-cerita lisan komunitas muslim di Kampung Gelgel secara turun temurun. Seperti dicatat buku Bulan Sabit di Pulau Dewata, Jejak Kampung Islam Kusamba-Bali, tulisan I Gde Parimartha, Ida Bagus Gde Putra, dan Luh Pt.Kusuma Ririen, warga Islam yang pertama kali datang ke Gelgel (sebagai pusat pemerintahan di Bali sejak abad XIV) adalah rombongan pengiring raja sejumlah 40 orang dari Kerajaan Majapahit. Peristiwa itu terjadi pada masa pemerintahan Raja Gelgel I, Ketut Ngalesir.

Sumber lain, dari Babad Dalem, menyebutkan yang berbeda. Bahwa pengislaman di Bali dilakukan oleh utusan dari Mekah ke kerajaan Bali pada masa pemerintahan Dalem Waturenggong, sekitar abad ke-16. 

Hanya saja sumber itu tidak merinci lebih jauh, nama utusan dan kapan utusan tersebut datang menghadap raja. “Jika menilik sejarah, pada abad ke-15 dan ke-16 ada dua pusat kerajaan Islam di Jawa, yaitu Demak dan Mataram,” tulis historia.id.

Jika melihat bahwa Demak saat itu menjadi pusat penyebaran agama Islam, sehingga diberi julukan kota Mekah di kawasan Nusantara, Mekah yang dimaksud sumber tadi kemungkinan besar merujuk ke Kerajaan Demak di Jawa. 

Sedangkan Dalem Waturenggong merupakan penerus Dalem Ngalesir. Abad itu juga menjadi puncak kejayaan Islam di Nusantara. Sementara kerajaan-kerajaan Hindu-Buddha, termasuk Majapahit, pengaruhnya kian surut akibat banyak kerajaan yang mulai menerima keberadaan agama Islam di wilayahnya.