Kesultanan Sulu adalah sebuah pemerintahan Muslim yang pernah menguasai Laut Sulu di Filipina Selatan. Kesultanan ini didirikan pada tahun 1450. Pada zaman kegemilangannya, negeri ini telah memperluas perbatasannya dari Mindanao hingga bagian timur negeri Sabah (sekarang bagian dari Sabah dan Kalimantan Utara).
Kesultanan Sulu didirikan pada 17 November 1405[1] oleh seorang penjelajah kelahiran Johor dan ulamaSharif ul-Hashim. Paduka Mahasari Maulana al Sultan Sharif ul-Hashim menjadi nama lengkap pemerintahannya, Sharif-ul Hashim adalah singkatannya. Dia menetap di Buansa, Sulu. Setelah perkawinan Abu Bakar dan dayang-dayang (putri) setempat Paramisuli, ia mendirikan kesultanan. Kesultanan memperoleh kemerdekaannya dari Kekaisaran Brunei pada tahun 1578.
Wilayah Kesultanan Sulu saat ini pernah berada di bawah pengaruh Kekaisaran Brunei sebelum memperoleh kemerdekaannya sendiri pada tahun 1578.[2] Setelah itu, permukiman paling awal yang diketahui di daerah ini segera ditempati oleh kesultanan yang berada di Maimbung, Jolo. Pada waktu itu, Sulu dipanggil dengan nama Lupah Sug [en].
Pada tahun 1380, seorang ulama keturunan Arab, Makhdum Karim memperkenalkan Islam di Kepulauan Sulu. Kemudian tahun 1390, Raja Bagindo yang berasal dari Minangkabau[3] melanjutkan penyebaran Islam di wilayah ini. Hingga akhir hayatnya Raja Bagindo telah mengislamkan masyarakat Sulu sampai ke Pulau Sibutu.[4]
Sekitar tahun 1450, seorang keturunan Arab dari Johor yaitu Syariful Hasyim Sayyid Abu Bakar tiba di Sulu. Ia kemudian menikah dengan Paramisuli, putri Raja Bagindo. Setelah kematian Raja Bagindo, Abu Bakar melanjutkan pengislaman di wilayah ini. Pada tahun 1457, ia memproklamirkan berdirinya Kesultanan Sulu dan memakai gelar "Paduka Maulana Mahasari Syarif Sultan Hasyim Abu Bakar". Gelar "Paduka" adalah gelar setempat yang berarti tuan sedangkan "Mahasari" bermaksud Yang Dipertuan.
Pada tahun 1703, Kesultanan Brunei memberikan bagian timur Sabah kepada Kesultanan Sulu atas bantuan mereka menumpas pemberontakan di Brunei. Pada tahun yang sama, Kesultanan Sulu memberikan Pulau Palawan kepada Sultan Qudarat dari Kesultanan Maguindanao sebagai hadiah perkawinan Sultan Qudarat dengan putri sultan Sulu dan juga sebagai hadiah persekutuan Maguindanao dengan Sulu. Sultan Qudarat akhirnya menyerahkan Palawan kepada Spanyol.