Следующей стадией исламизации Сулу было создание мусульманского султаната в середине XV в. Первым султаном Сулу считается Абу Бакр, принявший на троне мусульманский титул Шариф-уль-Хашим (полный титул включал также и местный традиционный титул — падука). Сведения о его жизни до прибытия на Сулу разноречивы, но во всех сулуанских тарсила указывается на арабское происхождение Абу Бакра, поскольку, согласно мусульманской традиции, султан должен принадлежать к прямым потомкам Пророка или по крайней мере быть выходцем из арабов. Наиболее распространена версия, по которой Абу Бакр в 30-е годы находился при дворе султана Малакки (возможно, был родственником султана), откуда перебрался в Палембанг (Суматра), затем в Бруней. Из Брунея Абу Бакр прибыл в Буанса, где вскоре женился на дочери раджи Багинда, принял титул султана в 1450 г., положив начало новой мусульманской династии на Сулу. Во время правления Абу Бакра, с 1450 по 1480 г., ислам превратился в государственную религию, началось формирование политических и социальных институтов, основанных на исламской традиции и шариате. Столица первого султана находилась в Буанса (при преемниках Абу Бакра она была перенесена в Холо). Территориально султанат объединял княжества Буанса и Холо, расположенные в приморских районах. С созданием султаната ускорился процесс исламизации населения горных территорий о-ва Холо, входивших в состав княжества буранунов.
Исламизация Минданао началась полтора столетия спустя — с середины XV в. К этому времени относятся сведения в местных тарсила о деятельности миссионеров с архипелага Сулу. В начале XVI в. проповедниками ислама на Минданао стали мусульманские эмигранты из Малайи. Известную роль в этом сыграл захват Малакки (1511 г.), в то время крупнейшего центра исламского мира в Юго-Восточной Азии, португальскими колонизаторами. Падение Малакки вызвало массовое бегство жителей, в том числе членов султанской семьи, придворных, знати, торговцев, устремившихся в соседние районы. Возможно, с этой миграцией было связано появление на Минданао шарифа Мухаммеда Кабунгсувана. На лодках морских кочевников-баджао он перебрался в Бруней, а в 1515 г. высадился в местечке Малабанг, на западном побережье Минданао. Согласно существовавшей традиции, шариф занялся распространением ислама в долине Пуланги и вскоре основал султанат, став первым султаном Магинданао. Сведения в ранних тарсила воспроизводят, однако, несколько иное и более сложное развитие событий. Первоначально шарифу, встреченному враждебно местными дато, удалось установить контроль лишь над небольшой территорией в районе Малабанга. В дальнейшем с помощью политических союзов с дато Магинданао и Буайана, подкрепленных его браком с дочерью местного правителя, Кабунгсуван добился усиления своих позиций в долине Пуланги. Но Кабунгсуван не носил титула султана, а был крупным религиозным и влиятельным политическим деятелем.
