Islam is the most adhered religion in East Java, a province of Indonesia, embraced by 96.7% of the whole population. Throughout the history, East Java has been considered as one of the heartlands of Islam in Indonesia, where seen one of the earliest proliferation of Islam, and the establishment of the largest Islamic mass organization in Indonesia, Nahdlatul Ulama.
Islam was first introduced in East Java in the 11th century. The earliest evidence of the arrival of Islam in East Java is the existence of Islamic graves on behalf of Fatimah bint Maimun in Gresik in 1082, as well as numbers of Islamic tombs at the complex of Majapahit tomb in Troloyo. The spread of Islam in East Java is owing greatly to the role of Wali Songo, the legendary Sufi saints, during the 14th century. Five out of nine Wali Songo saints have played the decisive roles in the propagation of Islam in East Java, namely Sunan Ampel in Surabaya, Sunan Gresik (Malik Ibrahim) and Sunan Giri in Gresik, Sunan Drajat in Lamongan, and Sunan Bonang in Tuban. Wali Songo were the descendants of Islamic scholars originated in the Middle East, Central and South Asia, and they came down to East Java after the generations of proselytization throughout the Southeast Asia such as Champa. Malik Ibrahim was the first of the saints moved across East Java for proselytization after the power of Majapahit Empire weakened. These saints had certain skills and mercantile interests they could provide to the local populations, such as the knowledge in irrigation, and able to guide and teach people regarding Islam at the same time. Among the first who converted to Islam were the fishermen in the port. These newly converted Muslims had founded their bases in mosques, such as Ampel Mosque in Surabaya which was completed in 1421, making it among the first mosques built in the archipelago.
Islam in East Java had been traditionally characterized by the preservation of local custom (adat) and the amalgamation of Islamic teaching with the practices of previous religions and indigenous cultures, resulting in the distinct style of Islamic tradition known as kejawen. Muslims who practice these syncretic forms of Islam were called abangan. More recently, kejawen has been relegated to rural pockets following the proliferation of Islamic orthodoxy in the late 20th century. At the same time, there has been a formation of Islam Nusantara which aimed at pluralist and vernacular interpretation of the orthodoxy.
Pesantren (or pondok pesantren) is the traditional Islamic seminary originated in East Java, in the form of gender-segregated boarding school. According to statistics in 2008, as many as 5,025 pesantrens spread across East Java. Some of the famous pesantrens in East Java are Pondok Modern Darussalam Gontor in Ponorogo, Pondok Pesantren Tebuireng in Jombang, and Pondok Pesantren Lirboyo in Kediri.
Several cities and regions in East Java are known as kota santri or the "city of Muslim students" and the center of Islamic education. Among the well-known kota santri are Gresik, Jombang, Kediri, Pasuruan, Ponorogo, Probolinggo, and Situbondo. The term kota santri is often emphasized by the cities and regions to promote religious tourism.