This article seeks to examine the theology of tolerance as the basis for interreligious and harmonious co-existence between Muslims and Hindus in Lombok. Lombok is known as the island of thousand mosques where majestic mosques scatter throughout the island. But Lombok is also a home for Hindus. The interactions between them have been very dynamics, creating integration, acculturation, adaptation, accommodation while sometimes also triggering tension. This article argues that theology occupies important aspects in both Hindu and Muslim daily live and thus can be employed as the solid basis of interreligious relations between them. From the Islamic perspective, there are a number of Qur’anic verse injuctions for tolerance. Hindus are also required to maintain tolerant attitude towards other religions as this is commanded in the Veda. These theological grounds will strengthen from the faith point of view Hindu-Muslim social cohesion, which has so far been realized though various means, such as music, arts and religious festivals.