A finales del siglo XIII, los estados costeros septentrionales de Sumatra comenzaron a convertirse al islam; el gobernador musulmán más antiguo que se conoce fue el sultán Malik al Saleh, de Pasai. La nueva religión, propagada en un primer momento por los mercaderes del sur de la India y de Gujarāt, se expandió lentamente hasta que el surgimiento del sultanato de Malaca en la costa occidental malaya le propinó un nuevo impulso. En el siglo XV la demanda europea de especias provenientes de las Molucas (o de las islas de las Especias) fue creciendo y hacia 1436 Malaca se había convertido en un importante emporio en la ruta comercial entre las Molucas y Occidente. Malaca, que tenía un gran poder político y comercial, fue también un centro de difusión del islam. En los siglos anteriores Singasari y Majapahit se hicieron cargo del comercio de los principados de la costa septentrional de Java que intercambiaban arroz por especias de las Molucas.