Kesultanan Sulu adalah sebuah kerajaan Muslim yang pernah suatu masa dahulu menguasai Laut Sulu di Filipina Selatan. Kerajaan ini didirikan pada tahun 1450. Ketika zaman kegemilangannya, negeri ini telah meluaskan sempadannya dari Mindanao sehingga ke negeri Sabah. Sekitar 1450an, seorang Arab dari Johor iaitu Shari'ful Hashem Syed Abu Bakr tiba di Sulu. Pada tahun 1457, beliau menubuhkan Kesultanan Sulu dan memakai gelaran "Paduka Maulana Mahasari Sharif Sultan Hashem Abu Bakr". Gelaran "Paduka" adalah gelaran tempatan yang bermaksud tuan manakala "Mahasari" bermaksud Yang DiPertuan.
Pada tahun 1703, Kesultanan Brunei menganugerahkan Sabah Timur kepada Kesultanan Sulu di atas bantuan mereka menumpaskan pemberontakan di Brunei. Pada tahun yang sama, Kesultanan Sulu menganugerahkan Pulau Palawan kepada Sultan Qudarat dari Kesultanan Maguindanao sebagai hadiah perkahwinan Sultan Qudarat dengan puteri Sulu dan juga sebagai hadiah persekutuan Maguindanao dengan Sulu. Sultan Qudarat kemudiannya menyerahkan Palawan kepada Sepanyol. (rujuk entri bawah).
