انتشر الإسلام على أيدي التجار العرب، وكان الإسلام أكثر نجاحًا من النصرانية في جزر الهند الشرقية؛ فقد انتشر الدين الإسلامي غالبًا بوساطة لغة الملايو، التي كانت تكتب بحروف عربية، والتي أدخلها المسلمون إلى منطقة إندونيسيا. وانتشرت لغة الملايو لتصبح لغة إندونيسيا الحديثة. وانتشر الإسلام تدريجيًا عبر الجزر الإندونيسية، ولا يزال انتشاره مستمرًا، وبذلك تبلغ نسبة المسلمين في إندونيسيا في الوقت الحاضر 85% من مجموع السكان، أما عددهم فيفوق نظيره في أية دولة إسلامية أخرى.
وصول البرتغاليين
وصل أول التجار الأوروبيين إلى جزر الهند الشرقية في مطلع القرن السادس عشر الميلادي. ولم يزرها من الأوروبيين قبل ذلك التاريخ سوى بعض الرحالة، فقد زارها ماركو بولو عام 1292م. وكان البرتغاليون أوائل الأوروبيين الذين أسسوا أول اتصال مستمر ومباشر مع إندونيسيا. ففي عام 1497م، أبحر المكتشف البرتغالي فاسكو دي جاما حول رأس الرجاء الصالح، واتجه شرقًا عبر المحيط الهندي إلى مياه كاليكَتْ على ساحل مالابار الهندي. وقد تبعه مكتشفون آخرون للبحث عن طرق جديدة لما كان يسميه الأوروبيون آنذاك"إنديس"أي إندونيسيا، في مطلع القرن السادس عشر.
وفي عام 1509م أرسل البرتغاليون أربع سفن تجارية إلى ملقا. وقد استقبلهم في البداية سلطانها بلطف وترحاب، إلا أنه خاف من تهديدهم لتجارته، فهاجمهم وأسر بعضهم. استولى البرتغاليون عام 1510م على جوُا على ساحل الهند الغربي. وفي عام 1511م قاد نائب الملك الجديد في المحيط الهندي ألفونصودي ألبوكيرك أسطولًا من جُوا إلى ملقا واستولى عليها. وبذلك تمكن البرتغاليون من السيطرة على التجارة في غربي إندونيسيا، وبنو حصونًا لهم فيها.