8 व्या शतकाच्या सुरुवातीस अरब मुस्लिम व्यापार्‍यांनी इंडोनेशियामध्ये प्रवेश केल्याचे पुरावे आहेत.^{[१९] [२०]} तथापि, १३ व्या शतकाच्या अखेरीस इस्लामचा प्रसार सुरू झाला नाही.^[१९] सुरुवातीला, इस्लामचा परिचय अरब मुस्लिम व्यापार्‍यांकडून झाला आणि नंतर विद्वानांनी मिशनरी क्रियाकलाप केला.स्थानिक राज्यकर्त्यांनी दत्तक घेतल्याने आणि उच्चभ्रूंच्या धर्मांतरामुळे याला आणखी मदत झाली.^[२०] मिशनरी अनेक देश आणि प्रदेशांतून आले होते, सुरुवातीला दक्षिण आशिया (म्हणजे गुजरात) आणि आग्नेय आशिया (म्हणजे चंपा) ^[२१] आणि नंतर दक्षिणेकडील अरबी द्वीपकल्प (म्हणजे हदरामौत) पासून.^[२०]13व्या शतकात, सुमात्राच्या उत्तरेकडील किनारपट्टीवर इस्लामिक राज्ये उदयास येऊ लागली.मार्को पोलो, 1292 मध्येचीनहून घरी जात असताना, किमान एक मुस्लिम शहर नोंदवले.^[२२] मुस्लीम राजवंशाचा पहिला पुरावा म्हणजे समुदेरा पासाई सल्तनतचा पहिला मुस्लिम शासक सुलतान मलिक अल सालेह याची 1297 ची समाधी.13व्या शतकाच्या अखेरीस, उत्तर सुमात्रामध्ये इस्लामची स्थापना झाली.14 व्या शतकापर्यंत, इस्लामची स्थापना ईशान्य मलाया, ब्रुनेई, नैऋत्य फिलीपिन्स आणि किनारी पूर्व आणि मध्य जावाच्या काही न्यायालयांमध्ये आणि 15 व्या शतकापर्यंत मलाक्का आणि मलय द्वीपकल्पातील इतर भागात झाली.^[२३] 15 व्या शतकात हिंदू जावानीज मजपाहित साम्राज्याचा ऱ्हास झाला, कारण अरबस्तान,भारत , सुमात्रा आणि मलय द्वीपकल्पातील मुस्लिम व्यापार्‍यांनी तसेच चीनने प्रादेशिक व्यापारावर वर्चस्व गाजवण्यास सुरुवात केली ज्यावर एकेकाळी जावानीज मजपाहित व्यापार्‍यांचे नियंत्रण होते.चिनी मिंग राजघराण्याने मलाक्काला पद्धतशीर पाठिंबा दिला.मिंग चायनीज झेंग हिच्या प्रवासाला (१४०५ ते १४३३) पालेमबांग आणि जावाच्या उत्तर किनार्‍यावर चिनी मुस्लिम वस्ती निर्माण करण्याचे श्रेय दिले जाते.^[२४] मलाक्काने सक्रियपणे या प्रदेशात इस्लाम धर्मात परिवर्तन करण्यास प्रोत्साहन दिले, तर मिंग फ्लीटने उत्तर किनारी जावामध्ये सक्रियपणे चीनी-मलय मुस्लिम समुदायाची स्थापना केली, त्यामुळे जावाच्या हिंदूंना कायमचा विरोध निर्माण झाला.1430 पर्यंत, मोहिमांनी जावाच्या उत्तरेकडील बंदरांवर जसे की सेमारंग, डेमाक, तुबान आणि अँपेल येथे मुस्लिम चीनी, अरब आणि मलय समुदायांची स्थापना केली होती;अशा प्रकारे, जावाच्या उत्तरेकडील किनारपट्टीवर इस्लामने पाय रोवण्यास सुरुवात केली.मलाक्का चायनीज मिंग संरक्षणाखाली भरभराट झाली, तर मजपाहितांना सतत मागे ढकलले गेले.^[२५] या काळातील प्रबळ मुस्लिम राज्यांमध्ये उत्तर सुमात्रामधील समुदेरा पासाई, पूर्व सुमात्रामधील मलाक्का सल्तनत, मध्य जावामधील डेमाक सल्तनत, दक्षिण सुलावेसीमधील गोवा सल्तनत आणि पूर्वेकडील मलुकू बेटांमधील टेरनेट आणि टिडोर या सल्तनतांचा समावेश होता.