O Sultanato de Sulu (Jawi: سلطنة سولو دار الإسلام) foi um Estado Islâmico Tausug que governava muitas das ilhas do Mar de Sulu, no sul das Filipinas e certas partes do atual Sabá (então Bornéu do Norte), especificamente "na costa noroeste se estende ao longo de toda a costa leste até o Rio Sibuco no sul e compreendendo entre outros os Estados do Paitan, Sugut e Bangaya, Labuk, Sandakan, Kina Batangan, Mumiang, e todos os outros territórios e estados ao sul do mesmo na fronteira com Baía de Darvel e, tanto quanto o rio Sibuco como todas as ilhas dentro de três léguas marinhas da costa".
O sultanato foi fundado em 1405
por Sayyid Abu Bakr Abirin, explorador árabe e estudante religioso, nascido em Johore que depois de se estabelecer em Banua Buansa Ummah (ummah é um termo árabe para "comunidade"), em Sulu. E após, o casamento de Abu Bakr e a local Dayang-Dayang (princesa) Paramisuli, ele fundou o sultanato e assumiu o título de Paduka Mahasari Maulana al Sultan Hashim ul-Sharif.
O poder temporal do sultanato foi abandonado em março de 1915 após os comandantes americanos negociarem com o Sultão Jamalul Kiram em nome do então governador-geral Francis Burton Harrison. Um acordo foi assinado e, posteriormente, foi chamado como o "Acordo Carpenter". Por este acordo, o sultão abandonou todo o poder temporal sobre o território, nas Filipinas (com exceção de algumas terras específicas concedidas ao Sultão Jamalul Kiram e seus herdeiros), mas manteve seus direitos de soberania sobre o território de Bornéu do Norte e sua autoridade religiosa como chefe titular da Igreja Islâmica no Sulu.
O mais antigo assentamento conhecido nas áreas que em breve seriam ocupadas pelo sultanato estavam em Maimbung, Jolo. Durante esse período, Sulu era chamado de Lupah Sug. O Principado de Maimbung, habitado por pessoas Buranun (ou Budanon, que significa, literalmente, "moradores da montanha"), foi governado pela primeira vez por um determinado rajá que assumiu o título de Rajá Sipad o Velho. De acordo com Majul, as origens do título rajá sipad tem origem na palavra Hindu shri paduka, que simboliza autoridade. O Principado foi instituído e regido através do sistema de rajás. Sipad o Velho foi sucedido por Sipad o Jovem.
Durante o reinado de Sipad o Jovem, um místico chamado Tuan Mashā'ikhachegando em Jolo, no ano de 1280 A.C. Pouco se sabe sobre as origens e a biografia precoce de Tuan Mashā'ikha, exceto que ele é um muçulmano, "que veio de terras estrangeiras" na liderança de uma frota de comerciantes muçulmanos.