دب النزاع بين الممالك البحرية والممالك البرية كالنزاع الذي وقع بين مملكتي سريفيجايا وماتارام. وأخذت هذه الدول القوية الجديدة الكثير من الأفكار الهندية فيما يتعلق بتنظيم الحكم واللغة، كما أظهرت القرى بعض التأثر بالهنود إذ كانت الأساطير الهندية تتلى في الوايانج، أي مسرح الدمى المتحركة والتي كانت تعرض في القرى.
جاء الإسلام إلى إندونيسيا مع التجار المسلمين من الهند والجزيرة العربية. وقد انتشر الإسلام تدريجيا بين الإندونيسيين؛ إذ بدأ يمد جذوره في إندونيسيا قبل انتهاء فترة النفوذ الهندي بوقت طويل. وفي العقد الأخير من القرن الثالث عشر الميلادي اعتنق أحد الحكام الإندونيسيين المحليين في شمالي سومطرة، ويدعى الملك الصالح الذي كان حاكما لباساي وأتباعه الإسلام. وزار الرحالة ابن بطوطة باساي عام ١٣٤٥م، فوجد سلطانها كريما، مولعا بالحوار الديني، متواضعا يذهب للمسجد أيام الجمعة. وقام هذا السلطان بإرسال البعثات الدينية لتدعو الناس حول باساي إلى الإسلام.
وكان الإسلام أكثر نجاحا من النصرانية في جزر الهند الشرقية؛ فقد انتشر الدين الإسلامي غالبا بوساطة لغة الملايو، التي كانت تكتب بحروف عربية، والتي أدخلها المسلمون إلى منطقة إندونيسيا.
وانتشرت لغة الملايو لتصبح لغة إندونيسيا الحديثة. وانتشر الإسلام تدريجيا عبر الجزر الإندونيسية، ولا يزال انتشاره مستمرا، وبذلك تبلغ نسبة المسلمين في إندونيسيا في الوقت الحاضر ٨٥% من مجموع السكان، أما عددهم فيفوق نظيره في أية دولة إسلامية أخرى.
وصل أول التجار الأوروبيين إلى جزر الهند الشرقية في مطلع القرن السادس عشر الميلادي. ولم يزرها من الأوروبيين قبل ذلك التاريخ سوى بعض الرحالة، فقد زارها ماركو بولو عام ١٢٩٢م. وكان البرتغاليون أوائل الأوروبيين الذين أسسوا أول اتصال مستمر ومباشر مع إندونيسيا. ففي عام ١٤٩٧م.