Terdapat bukti pedagang Muslim Arab memasuki Indonesia pada awal abad ke-8.^{[19] [20]} Namun, penyebaran Islam baru dimulai pada akhir abad ke-13.^[19] Mula-mula Islam masuk melalui pedagang Muslim Arab, kemudian kegiatan dakwah oleh para ulama.Hal ini lebih lanjut dibantu oleh adopsi oleh penguasa lokal dan konversi para elit.^[20] Para misionaris berasal dari beberapa negara dan wilayah, awalnya dari Asia Selatan (yaitu Gujarat) dan Asia Tenggara (yaitu Champa), ^[21] dan kemudian dari Semenanjung Arab bagian selatan (yaitu Hadhramaut).^[20]Pada abad ke-13, politik Islam mulai bermunculan di pesisir utara Sumatera.Marco Polo, dalam perjalanan pulang dariTiongkok pada tahun 1292, melaporkan setidaknya satu kota Muslim.^[22] Bukti pertama keberadaan dinasti Muslim adalah nisan bertanggal 1297 M, milik Sultan Malik al Saleh, penguasa Muslim pertama di Kesultanan Samudera Pasai.Pada akhir abad ke-13, Islam telah mapan di Sumatera Utara.Pada abad ke-14, Islam telah berkembang di timur laut Malaya, Brunei, Filipina barat daya, dan di beberapa wilayah pesisir Jawa Timur dan Tengah, dan pada abad ke-15, di Malaka dan wilayah lain di Semenanjung Malaya.^[23] Abad ke-15 menyaksikan kemunduran Kerajaan Majapahit Hindu Jawa, ketika pedagang Muslim dari Arab,India , Sumatra dan Semenanjung Malaya, dan juga Tiongkok mulai mendominasi perdagangan regional yang pernah dikuasai oleh pedagang Majapahit Jawa.Dinasti Ming Tiongkok memberikan dukungan sistematis kepada Malaka.Pelayaran Ming Tiongkok Zheng He (1405 hingga 1433) dipuji karena menciptakan pemukiman Muslim Tionghoa di Palembang dan pantai utara Jawa.^[24] Malaka secara aktif mendorong masuknya Islam di wilayah tersebut, sementara armada Ming secara aktif membentuk komunitas Muslim Tionghoa-Melayu di pesisir utara Jawa, sehingga menciptakan perlawanan permanen terhadap umat Hindu di Jawa.Pada tahun 1430, ekspedisi tersebut telah membentuk komunitas Muslim Tionghoa, Arab, dan Melayu di pelabuhan utara Jawa seperti Semarang, Demak, Tuban, dan Ampel;Dengan demikian, Islam mulai mendapat pijakan di pesisir utara Jawa.Malaka menjadi makmur di bawah perlindungan Ming Tiongkok, sementara Majapahit terus-menerus didesak mundur.^[25] Kerajaan Muslim yang dominan pada masa ini antara lain Samudera Pasai di Sumatera bagian utara, Kesultanan Malaka di Sumatera bagian timur, Kesultanan Demak di Jawa tengah, Kesultanan Gowa di Sulawesi bagian selatan, dan kesultanan Ternate dan Tidore di Kepulauan Maluku di sebelah timur.