অষ্টম শতাব্দীর প্রথম দিকে আরব মুসলিম ব্যবসায়ীদের ইন্দোনেশিয়ায় প্রবেশের প্রমাণ পাওয়া যায়।^{[১৯] [২০]} যাইহোক, ১৩ শতকের শেষের দিকে ইসলামের প্রসার শুরু হয়নি।^[১৯] প্রথমে আরব মুসলিম ব্যবসায়ীদের মাধ্যমে ইসলামের প্রবর্তন করা হয় এবং তারপর পণ্ডিতদের দ্বারা ধর্মপ্রচারক কার্যকলাপ।এটি স্থানীয় শাসকদের দ্বারা গ্রহণ এবং অভিজাতদের ধর্মান্তর দ্বারা আরও সহায়তা করেছিল।^[২০] ধর্মপ্রচারকদের উদ্ভব হয়েছিল বিভিন্ন দেশ ও অঞ্চল থেকে, প্রাথমিকভাবে দক্ষিণ এশিয়া (অর্থাৎ গুজরাট) এবং দক্ষিণ-পূর্ব এশিয়া (অর্থাৎ চম্পা), ^[২১] এবং পরে দক্ষিণ আরব উপদ্বীপ (অর্থাৎ হাধরামৌত) থেকে।^[২০]13শ শতাব্দীতে, সুমাত্রার উত্তর উপকূলে ইসলামি রাজনীতির উত্থান শুরু হয়।মার্কো পোলো, 1292 সালেচীন থেকে বাড়ি ফেরার পথে, অন্তত একটি মুসলিম শহরের খবর দিয়েছে।^[২২] মুসলিম রাজবংশের প্রথম প্রমাণ হল সামুদেরা পাসাই সালতানাতের প্রথম মুসলিম শাসক সুলতান মালিক আল সালেহ-এর সমাধিস্থল।13 শতকের শেষের দিকে, উত্তর সুমাত্রায় ইসলাম প্রতিষ্ঠিত হয়েছিল।14 শতকের মধ্যে, ইসলাম উত্তর-পূর্ব মালয়, ব্রুনাই, দক্ষিণ-পশ্চিম ফিলিপাইনে এবং উপকূলীয় পূর্ব ও মধ্য জাভার কিছু আদালতের মধ্যে এবং 15 শতকের মধ্যে মালাক্কা এবং মালয় উপদ্বীপের অন্যান্য অঞ্চলে প্রতিষ্ঠিত হয়েছিল।^[২৩] 15ম শতাব্দীতে হিন্দু জাভানিজ মাজাপাহিত সাম্রাজ্যের পতন দেখা যায়, কারণ আরব,ভারত , সুমাত্রা এবং মালয় উপদ্বীপের মুসলিম ব্যবসায়ীরা এবং চীনও আঞ্চলিক বাণিজ্যে আধিপত্য বিস্তার করতে শুরু করে যা একসময় জাভানিজ মাজাপাহিত ব্যবসায়ীদের দ্বারা নিয়ন্ত্রিত ছিল।চীনা মিং রাজবংশ মালাক্কাকে পদ্ধতিগত সহায়তা প্রদান করেছিল।পালেমবাং এবং জাভার উত্তর উপকূলে চীনা মুসলিম বসতি তৈরির জন্য মিং চাইনিজ ঝেং হি এর সমুদ্রযাত্রা (1405 থেকে 1433) কৃতিত্বপূর্ণ।^[২৪] মালাক্কা সক্রিয়ভাবে এই অঞ্চলে ইসলাম ধর্মে ধর্মান্তরিত করতে উৎসাহিত করেছিল, যখন মিং নৌবহর সক্রিয়ভাবে উত্তর উপকূলীয় জাভাতে চীনা-মালয় মুসলিম সম্প্রদায় প্রতিষ্ঠা করেছিল, এইভাবে জাভার হিন্দুদের একটি স্থায়ী বিরোধিতা তৈরি করেছিল।1430 সালের মধ্যে, অভিযানগুলি জাভার উত্তর বন্দর যেমন সেমারাং, দেমাক, তুবান এবং অ্যাম্পেলে মুসলিম চীনা, আরব এবং মালয় সম্প্রদায় স্থাপন করেছিল;এইভাবে, ইসলাম জাভার উত্তর উপকূলে পা রাখতে শুরু করে।মালাক্কা চীনা মিং সুরক্ষার অধীনে উন্নতি লাভ করেছিল, যখন মাজাপাহিতরা স্থিরভাবে পিছনে ঠেলেছিল।^[২৫] এই সময়ে প্রভাবশালী মুসলিম রাজ্যগুলির মধ্যে রয়েছে উত্তর সুমাত্রার সামুদেরা পাসাই, পূর্ব সুমাত্রার মালাক্কা সালতানাত, মধ্য জাভাতে দেমাক সালতানাত, দক্ষিণ সুলাওয়েসিতে গোওয়া সালতানাত এবং পূর্বে মালুকু দ্বীপপুঞ্জের টারনেট ও টিডোর সালতানাত।