Perkataan "Samudera" berasal daripada perkataan Sanskrit, iaitu Samundra atau Samandara, yang membawa pengertian "lautan". Menurut Hikayat Raja-raja Pasai, Merah Silu dikatakan ternampak seekor semut sebesar kucing. Baginda menangkap dan memakannya lalu menamai tempat itu sebagai "Samandara". Merah Silu yang menjadi raja pada tahun 1267 kemudian memeluk agama Islam dan menukarkan namanya menjadi Malikussalih. Makam Sultan Malikussalih bertarikh 1297 ditulis sepenuhnya dalam Bahasa Arab dan sekarang ini masih boleh didapati di desa Beuringin, Kecamatan Samudera, Aceh Utara.

Berdasarkan Hikayat Raja-raja Pasai, menceritakan tentang pendirian Pasai oleh Merah Silu, sesudah sebelumnya ia menyingkirkan seorang raja yang bernama Sultan Malik al-Nasser. Merah Silu ini sebelumnya berada pada satu kawasan yg disebut dengan Semerlanga kemudian sesudah naik tahta bergelar Sultan Malik as-Saleh, ia wafat pada tahun 696 H atau 1297 M.

Dalam Hikayat Raja-raja Pasai mahupun Sulalatus Salatin nama Pasai & Samudera telah dipisahkan merujuk pada dua kawasan yang berbeza, namun dalam catatan Tiongkok nama-nama tersebut tak dibezakan sama sekali. Marco Polo dalam lawatannya mencatat beberapa daftar kerajaan yang ada di Pantai Timur Pulau Sumatera waktu itu, dari selatan ke utara terdapat nama Ferlec (Perlak), Basma dan Samara [Samudera]. Pemerintahan Sultan Malik as-Saleh kemudian dilanjutkan oleh puteranya Sultan Muhammad Malik az-Zahir dari perkawinannya dengan puteri Raja Perlak. Pada masa pemerintahan Sultan Muhammad Malik az-Zahir, koin emas sebagai mata wang telah diperkenalkan di Pasai, seiring dengan berkembangnya Pasai menjadi salah satu kawasan perdagangan sekaligus tempat pengembangan dakwah agama Islam.

Sekitar tahun 1326 ia meninggal dunia dan digantikan oleh anaknya Sultan Mahmud Malik az-Zahir dan memerintah sampai tahun 1345. Pada masa pemerintahannya, ia dikunjungi oleh Ibn Batuta, kemudian menceritakan bahawa sultan di negeri Samatrah [Samudera] menyambutnya dengan penuh keramahan, & penduduknya menganut Mazhab Syafi’i.

Selanjutnya pada masa pemerintahan Sultan Ahmad Malik az-Zahir putera Sultan Mahmud Malik az-Zahir, datang serangan dari Majapahit antara tahun 1345 dan 1350, menyebabkan Sultan Pasai terpaksa melarikan diri dari ibu kota kerajaan. Kesultanan Pasai juga dikenali dengan nama Samudera Darussalam, atau Samudera Pasai, ialah kerajaan Islam yang terletak di pesisir pantai utara Sumatera, terletak di sekitar Kota Lhokseumawe dan Aceh Utara, Provinsi Aceh, Indonesia.