Malik ul Salih (Malik Al Saleh, Malik al Salih or Malik ul Saleh) established the first Muslim state of Samudera Pasai in the year 1267. His original name was Mara Silu, Merah Silu, or Muerah Silu. It was said he saw an ant as big as a cat, he caught it and ate it. He named the place Samudera, meaning ocean in Sanskrit (samudra). King Mara Silu later converted to Islam, given an Ayyubid name of Malik Al-Salih. He married neighbour Perlak (Peureulak) Kingdom's daughter and had two sons. According to Hikayat Raja-raja Pasai, he met Muhammad in dream thus accepts conversion of Islam. Another source claimed a prince Malik from Aceh sailed across the sea to Beruas (Gangga Negara) and established a sultanate there.
According to Islamic Council of Victoria ICV, historians argue "that by the beginning of the 9th century Arab merchants and sailors, (and other Muslims) had begun to dominate Nanhai (Guangzhou) or Southeast Asian Trade." However, Malik's tomb is the oldest evidence known of the establishment in Indonesia.