Terdapat bukti pedagang Islam Arab memasuki Indonesia seawal abad ke-8.^{[19] [20]} Namun begitu, pada penghujung abad ke-13 penyebaran Islam bermula.^[19] Pada mulanya, Islam diperkenalkan melalui pedagang Muslim Arab, dan kemudian aktiviti dakwah oleh ulama.Ia dibantu lagi dengan pengambilan anak angkat oleh pemerintah tempatan dan penukaran agama golongan elit.^[20] Para mubaligh berasal dari beberapa negara dan wilayah, pada mulanya dari Asia Selatan (iaitu Gujerat) dan Asia Tenggara (iaitu Champa), ^[21] dan kemudiannya dari selatan Semenanjung Arab (iaitu Hadhramaut).^[20]Pada abad ke-13, politik Islam mula muncul di pantai utara Sumatera.Marco Polo, dalam perjalanan pulang dariChina pada 1292, melaporkan sekurang-kurangnya satu bandar Islam.^[22] Bukti pertama dinasti Muslim ialah batu nisan, bertarikh CE 1297, Sultan Malik al Saleh, pemerintah Islam pertama Kesultanan Samudera Pasai.Pada akhir abad ke-13, Islam telah bertapak di Sumatera Utara.Menjelang abad ke-14, Islam telah bertapak di timur laut Malaya, Brunei, barat daya Filipina , dan di antara beberapa mahkamah di pesisir pantai Jawa Timur dan Tengah, dan menjelang abad ke-15, di Melaka dan kawasan lain di Semenanjung Tanah Melayu.^[23] Abad ke-15 menyaksikan kemerosotan Empayar Majapahit Jawa Hindu, apabila pedagang Islam dari Arab,India , Sumatera dan Semenanjung Tanah Melayu, dan juga China mula menguasai perdagangan serantau yang pernah dikuasai oleh pedagang Majapahit Jawa.Dinasti Ming Cina memberikan sokongan sistematik kepada Melaka.Pelayaran Zheng He Cina Ming (1405 hingga 1433) dikreditkan kerana mewujudkan penempatan Muslim Cina di Palembang dan pantai utara Jawa.^[24] Melaka secara aktif menggalakkan penukaran agama kepada Islam di rantau ini, manakala armada Ming secara aktif menubuhkan komuniti Cina-Melayu Islam di utara pantai Jawa, sekali gus mewujudkan penentangan kekal kepada Hindu di Jawa.Menjelang 1430, ekspedisi telah menubuhkan masyarakat Cina, Arab dan Melayu Islam di pelabuhan utara Jawa seperti Semarang, Demak, Tuban, dan Ampel;dengan itu, Islam mula bertapak di pantai utara Jawa.Melaka makmur di bawah perlindungan Ming Cina, manakala Majapahit terus diundur.^[25] Kerajaan-kerajaan Islam yang dominan pada masa ini termasuk Samudera Pasai di utara Sumatera, Kesultanan Melaka di timur Sumatera, Kesultanan Demak di Jawa tengah, Kesultanan Gowa di Sulawesi selatan, dan kesultanan Ternate dan Tidore di Kepulauan Maluku di sebelah timur.