Vuonna 1511 Malakka joutui portugalilaisten käsiin ja sulttaani Mahmud Shah pakotettiin pakenemaan Malakasta.Sulttaani yritti useita yrityksiä vallata pääkaupunki takaisin, mutta hänen ponnistelunsa olivat turhia.Portugalilaiset kostivat ja pakottivat sulttaanin pakenemaan Pahangiin.Myöhemmin sulttaani purjehti Bintaniin ja perusti sinne uuden pääkaupungin.Kun tukikohta oli perustettu, sulttaani kokosi sekavat malaijilaiset joukot ja järjesti useita hyökkäyksiä ja saartoja Portugalin asemaa vastaan.Pekan Tuassa, Sungai Telurissa, Johorissa, Johorin sulttaanikunnan perusti Raja Ali Ibni Sulttaani Mahmud Melaka, joka tunnettiin nimellä sulttaani Alauddin Riayat Shah II (1528–1564), vuonna 1528. ^[53] Vaikka sulttaani Alauddin Riayat Shah ja hänen seuraajansa joutuivat taistelemaan portugalilaisten hyökkäyksiä vastaan ​​Malakassa ja acehnesilaisten hyökkäyksiä vastaan ​​Sumatralla, ja he onnistuivat säilyttämään otteensa Johorin sulttaanivaltiossa.Toistuvat ryöstöt Malackaan aiheuttivat portugalilaisille vakavia vaikeuksia ja auttoivat portugalilaisia ​​tuhoamaan maanpaossa olevan sulttaanin joukot.Malaijilaisia ​​yritettiin tukahduttaa useaan otteeseen, mutta vasta vuonna 1526 portugalilaiset lopulta tuhosivat Bintanin maan tasalle.Sitten sulttaani vetäytyi Kampariin Sumatralle ja kuoli kaksi vuotta myöhemmin.Hän jätti jälkeensä kaksi poikaa nimeltä Muzaffar Shah ja Alauddin Riayat Shah II.^[53] Muzaffar Shah jatkoi Perakin perustamista, kun taas Alauddin Riayat Shahista tuli Johorin ensimmäinen sulttaani.^[53]