Има доказателства за арабски мюсюлмански търговци, навлезли в Индонезия още през 8 век.^{[19] [20]} Въпреки това, едва в края на 13 век започва разпространението на исляма.^[19] Отначало ислямът е въведен чрез арабски мюсюлмански търговци, а след това мисионерската дейност от учени.То беше допълнително подпомогнато от осиновяването от местните владетели и обръщането на елитите.^[20] Мисионерите произхождат от няколко страни и региони, първоначално от Южна Азия (т.е. Гуджарат) и Югоизточна Азия (т.е. Чампа), ^[21] и по-късно от южния Арабски полуостров (т.е. Хадрамаут).^[20]През 13-ти век ислямските политици започват да се появяват на северното крайбрежие на Суматра.Марко Поло, на път за дома си отКитай през 1292 г., съобщава за поне един мюсюлмански град.^[22] Първото доказателство за мюсюлманска династия е надгробният камък, датиран от 1297 г., на султан Малик ал Салех, първият мюсюлмански владетел на султаната Самудера Пасай.До края на 13 век ислямът е установен в Северна Суматра.До 14 век ислямът е установен в североизточна Малая, Бруней, югозападните Филипини и сред някои дворове на крайбрежната Източна и Централна Ява, а до 15 век в Малака и други области на Малайския полуостров.^[23] През 15-ти век се вижда упадъкът на индуистката яванска империя Маджапахит, тъй като мюсюлмански търговци от Арабия,Индия , Суматра и Малайския полуостров, а също и Китай започват да доминират регионалната търговия, която някога е била контролирана от явански търговци Маджапахит.Китайската династия Мин осигурява системна подкрепа на Малака.Пътешествията на китайския Минг Джън Хе (1405 до 1433 г.) се смятат за създаването на китайско мюсюлманско селище в Палембанг и северното крайбрежие на Ява.^[24] Малака активно насърчава приемането на исляма в региона, докато флотът на Минг активно създава китайско-малайска мюсюлманска общност в северната крайбрежна част на Ява, създавайки по този начин постоянна опозиция срещу индусите на Ява.До 1430 г. експедициите са установили мюсюлмански китайски, арабски и малайски общности в северните пристанища на Ява като Семаранг, Демак, Тубан и Ампел;по този начин ислямът започва да се налага в северното крайбрежие на Ява.Малака просперира под защитата на китайците Минг, докато Маджапахитите са постоянно отблъснати.^[25] Доминиращите мюсюлмански кралства през това време включват Samudera Pasai в северна Суматра, султанат Малака в източна Суматра, султанат Demak в централна Ява, султанат Gowa в южната част на Сулавеси и султанатите Ternate и Tidore в островите Maluku на изток.