अरब मुस्लिम व्यापारियों के 8वीं शताब्दी की शुरुआत में इंडोनेशिया में प्रवेश करने के प्रमाण मिलते हैं।^{[19] [20]} हालाँकि, 13वीं शताब्दी के अंत तक इस्लाम का प्रसार शुरू नहीं हुआ था।^[19] सबसे पहले, इस्लाम अरब मुस्लिम व्यापारियों के माध्यम से पेश किया गया था, और फिर विद्वानों द्वारा मिशनरी गतिविधि।स्थानीय शासकों द्वारा इसे अपनाने और कुलीन वर्ग के धर्म परिवर्तन से इसे और सहायता मिली।^[20] मिशनरियों की उत्पत्ति कई देशों और क्षेत्रों से हुई थी, शुरू में दक्षिण एशिया (यानी गुजरात) और दक्षिण पूर्व एशिया (यानी चंपा), ^[21] और बाद में दक्षिणी अरब प्रायद्वीप (यानी हद्रामौत) से।^[20]13वीं शताब्दी में, सुमात्रा के उत्तरी तट पर इस्लामी राजनीति उभरने लगी।1292 मेंचीन से घर जाते समय मार्को पोलो ने कम से कम एक मुस्लिम कस्बे की सूचना दी।^[22] मुस्लिम राजवंश का पहला साक्ष्य समुदेरा पसाई सल्तनत के पहले मुस्लिम शासक सुल्तान मलिक अल सालेह की कब्रगाह है, जो 1297 ई. की है।13वीं सदी के अंत तक उत्तरी सुमात्रा में इस्लाम की स्थापना हो चुकी थी।14वीं शताब्दी तक, इस्लाम पूर्वोत्तर मलाया, ब्रुनेई, दक्षिण-पश्चिमी फिलीपींस और तटीय पूर्व और मध्य जावा की कुछ अदालतों में स्थापित हो चुका था, और 15वीं शताब्दी तक, मलक्का और मलय प्रायद्वीप के अन्य क्षेत्रों में स्थापित हो चुका था।^[23] 15वीं शताब्दी में हिंदू जावानीस माजापहित साम्राज्य का पतन देखा गया, क्योंकि अरब,भारत , सुमात्रा और मलय प्रायद्वीप के मुस्लिम व्यापारियों और चीन ने भी क्षेत्रीय व्यापार पर हावी होना शुरू कर दिया था, जो कभी जावानीस माजापहित व्यापारियों द्वारा नियंत्रित किया जाता था।चीनी मिंग राजवंश ने मलक्का को व्यवस्थित सहायता प्रदान की।मिंग चीनी झेंग हे की यात्राओं (1405 से 1433) को पालेम्बैंग और जावा के उत्तरी तट में चीनी मुस्लिम बस्ती बनाने का श्रेय दिया जाता है।^[24] मलक्का ने सक्रिय रूप से क्षेत्र में इस्लाम में रूपांतरण को प्रोत्साहित किया, जबकि मिंग बेड़े ने सक्रिय रूप से उत्तरी तटीय जावा में चीनी-मलय मुस्लिम समुदाय की स्थापना की, इस प्रकार जावा के हिंदुओं के लिए एक स्थायी विरोध पैदा हुआ।1430 तक, अभियानों ने जावा के उत्तरी बंदरगाहों जैसे सेमारंग, डेमक, टुबन और एम्पेल में मुस्लिम चीनी, अरब और मलय समुदायों की स्थापना की थी;इस प्रकार, इस्लाम ने जावा के उत्तरी तट पर पैर जमाना शुरू कर दिया।मलक्का चीनी मिंग संरक्षण के तहत समृद्ध हुआ, जबकि मजापहित को लगातार पीछे धकेल दिया गया।^[25] इस समय के दौरान प्रमुख मुस्लिम राज्यों में उत्तरी सुमात्रा में समुदेरा पासाई, पूर्वी सुमात्रा में मलक्का सल्तनत, मध्य जावा में डेमक सल्तनत, दक्षिणी सुलावेसी में गोवा सल्तनत और पूर्व में मालुकु द्वीप में टर्नेट और टिडोर की सल्तनत शामिल थे।