มีหลักฐานว่าพ่อค้ามุสลิมอาหรับเข้ามาในประเทศอินโดนีเซียตั้งแต่ต้นศตวรรษที่ 8^{[19] [20]} อย่างไรก็ตาม จนกระทั่งปลายศตวรรษที่ 13 การเผยแพร่ศาสนาอิสลามจึงเริ่มต้นขึ้น^[19] ในตอนแรก ศาสนาอิสลามได้รับการแนะนำผ่านพ่อค้ามุสลิมอาหรับ และจากนั้นก็มีนักวิชาการเผยแพร่กิจกรรมมิชชันนารีโดยได้รับความช่วยเหลือเพิ่มเติมจากการที่ผู้ปกครองท้องถิ่นยอมรับและการเปลี่ยนใจเลื่อมใสของชนชั้นสูง^[20] มิชชันนารีมีต้นกำเนิดมาจากหลายประเทศและภูมิภาค เริ่มแรกจากเอเชียใต้ (เช่น คุชราต) และเอเชียตะวันออกเฉียงใต้ (เช่น จำปา) ^[21] และต่อมามาจากคาบสมุทรอาหรับตอนใต้ (เช่น ฮัดห์ราเมาต์)^[20]ในศตวรรษที่ 13 การเมืองอิสลามเริ่มปรากฏบนชายฝั่งทางตอนเหนือของเกาะสุมาตรามาร์โค โปโล ระหว่างเดินทางกลับบ้านจากประเทศจีน ในปี 1292 รายงานเมืองมุสลิมอย่างน้อยหนึ่งเมือง^[22] หลักฐานชิ้นแรกที่แสดงถึงราชวงศ์มุสลิมคือป้ายหลุมศพ ลงวันที่ CE 1297 ของสุลต่าน มาลิก อัล ซาเลห์ ผู้ปกครองมุสลิมคนแรกของสุลต่านซามูเดรา ปาไซในตอนท้ายของศตวรรษที่ 13 ศาสนาอิสลามได้ก่อตั้งขึ้นในเกาะสุมาตราตอนเหนือเมื่อถึงคริสต์ศตวรรษที่ 14 ศาสนาอิสลามได้สถาปนาขึ้นในแหลมมลายูตะวันออกเฉียงเหนือ บรูไน ฟิลิปปินส์ ตะวันตกเฉียงใต้ และในราชสำนักบางแห่งของชายฝั่งตะวันออกและชวากลาง และภายในคริสต์ศตวรรษที่ 15 ใน มะละกา และพื้นที่อื่นๆ ของคาบสมุทรมลายู^{[คริสต์]} ศตวรรษที่ 15 จักรวรรดิมัชปาหิตของชาวฮินดูชวาเสื่อมถอยลง เนื่องจากพ่อค้าชาวมุสลิมจากอาระเบียอินเดีย สุมาตรา และคาบสมุทรมลายู และจีนก็เริ่มครอบงำการค้าในภูมิภาคที่ครั้งหนึ่งเคยถูกควบคุมโดยพ่อค้าชาวมัชปาหิตชาวชวาราชวงศ์หมิง ของจีนให้การสนับสนุนมะละกาอย่างเป็นระบบการเดินทางของ Ming Chinese Zheng He (1405 ถึง 1433) ได้รับการยกย่องในการสร้างชุมชนชาวจีนมุสลิมในปาเล็มบังและชายฝั่งทางเหนือของเกาะชวา^[24] มะละกาสนับสนุนการเปลี่ยนมานับถือศาสนาอิสลามอย่างแข็งขันในภูมิภาค ในขณะที่กองเรือหมิงได้ก่อตั้งชุมชนมุสลิมจีน-มาเลย์อย่างแข็งขันในชวาชายฝั่งตอนเหนือ จึงเป็นการสร้างการต่อต้านชาวฮินดูในชวาอย่างถาวรภายในปี 1430 คณะสำรวจได้ก่อตั้งชุมชนชาวจีนมุสลิม อาหรับ และมาเลย์ขึ้นที่ท่าเรือทางตอนเหนือของชวา เช่น เซมารัง เดมัก ตูบัน และอัมเปลด้วยเหตุนี้ อิสลามจึงเริ่มเข้ามาตั้งหลักในชายฝั่งทางตอนเหนือของเกาะชวามะละกาเจริญรุ่งเรืองภายใต้การคุ้มครองของราชวงศ์หมิง ในขณะที่มัชปาหิตถูกผลักกลับอย่างต่อเนื่อง^[25] อาณาจักรมุสลิมที่ปกครองในช่วงเวลานี้ ได้แก่ ซามูเดรา ปาไซทางตอนเหนือของเกาะสุมาตรา, รัฐสุลต่านมะละกาในสุมาตราตะวันออก, สุลต่านเดมักในชวาตอนกลาง, สุลต่านโกวาทางตอนใต้ของสุลาเวสี และสุลต่านแห่งเตอร์นาเตและติโดเรในหมู่เกาะมาลุกกะทางตะวันออก