Kedatangan orang Melayu ke Pulau Bali direkodkan pada tahun 1669 apabila empat ulama dan pengikutnya tiba di Jembrana untuk menyebarkan ajaran Islam di Bali. Misi ini telah diizinkan oleh Raja Jembrana iaitu I Gusti Arya Pancoran. Empat ulama tersebut ialah Dawan Sirajuddin dari Sarawak, Empayar Brunei; Syeikh Basir dari Yaman, Empayar Uthmaniyyah; Mohammad Yasin dari Makassar; dan Syihabbudin yang juga berasal dari Makassar.[4][3]

Pada tahun 1799, empat buah kapal dari Kota Pontianak, Kesultanan Pontianak tiba di Jembrana dan disambut oleh Raja Jembrana iaitu Putu Seloka. Rombongan tersebut diketuai oleh Syarif Abdullah Yahya al-Qadri dan membawa seorang ulama dari Terengganu iaitu Muhammad Ya'qub. Oleh Raja Jembrana, kumpulan itu dibenarkan tinggal di atas tanah seluas 80 hektar di Loloan Barat (Loloan Barat) dan Loloan Timur (Lolan Timur).[4][3]

Bagaimanapun, menurut pembesar Loloan, Haji Achmad Damannuri, perkembangan masyarakat Melayu Bali adalah hasil pertemuan antara orang Bugis yang pada mulanya melarikan diri ke Perancak, Jembrana daripada mengejar VOC di Makassar pada tahun 1653 dengan seorang ulama dari Sarawak, Buyut Lebai, pada tahun 1675 yang mengajar agama Islam menggunakan bahasa Melayu sebagai bahasa pengantar. Orang Bugis kemudiannya mendapat persetujuan daripada Jembrana untuk menduduki kawasan Loloan.[5]

Satu lagi kajian yang dijalankan oleh ahli akademik Universiti Udayana bersetuju dengan naratif Haji Achmad Damannuri, mencadangkan bahawa orang Melayu Bali adalah hasil perkahwinan campur antara orang Bugis yang dibenarkan menetap di Loloan dan orang Bali yang tinggal di sekitarnya. Gelombang kedua pembentukan identiti Melayu Bali di Loloan dijelaskan oleh kedatangan pendatang dari Pontianak yang turut membawa kepada perkahwinan campur.[6] Menurut sumber lain, telah ditulis bahawa perbezaan antara majoriti Hindu Bali dan pendatang Islam sebenarnya memberi kesan kepada pengecualian pendatang ini.[3]