Muslim communities in the Hindu-majority area of Bali have existed since the 15th century. Since that period, the interdependence between the two religious communities has been something inevitable. This study aims to enrich the treasures of the interdependence discourse that exists between Muslims and Hindus in Bali. It tries to trace the history and early development of Islam in Bali, the relation pattern between Muslims and Hindus, and local wisdom influencing the interdependence in Bali. Data for this study were obtained through observations and interviews with key figures in Klungkung, Bali. After profound analysis, the writer concludes that the emergence of Islam in Bali occurred when Dalem Ketut Ngelesir (1380-1460) visited Majapahit during the vassal royal conference in early 1380 and brought 40 Muslim escorts. This period also marked the early Hindus-Muslim relationship in Bali with Klungkung as the first area with the Muslim community. Later, the relationship between Hindus and Muslims was maintained in the four consecutive periods: kingdom, colonization, post-independence, and the present. Among the local wisdom that has influenced the interdependence and integration between the two religious communities are megibung, ngejot, and religious activities such as the birth of Prophet Muhammad SAW., Nyepi, odalan, takbiran, and Eid al-Fitr.