Në 1511, Malacca ra në duart e portugezëve dhe Sulltan Mahmud Shah u detyrua të largohej nga Malacca.Sulltani bëri disa përpjekje për të rimarrë kryeqytetin, por përpjekjet e tij dështuan.Portugezët u hakmorrën dhe e detyruan sulltanin të ikte në Pahang.Më vonë, sulltani lundroi për në Bintan dhe themeloi një kryeqytet të ri atje.Me një bazë të krijuar, sulltani mblodhi forcat e rrënuara malajze dhe organizoi disa sulme dhe bllokada kundër pozicionit portugez.Me qendër në Pekan Tua, Sungai Telur, Johor, Sulltanati i Johorit u themelua nga Raja Ali Ibni Sulltan Mahmud Melaka, i njohur si Sulltan Alauddin Riayat Shah II (1528–1564), në 1528. ^[53] Edhe pse Sulltan Alauddin Riayat Shah dhe pasardhësi i tij iu desh të përballeshin me sulmet e portugezëve në Malacca dhe nga Acehnese në Sumatra, ata arritën të mbanin kontrollin e tyre në Sulltanatin Johor.Bastisjet e shpeshta në Malacca i shkaktuan portugezëve vështirësi të rënda dhe kjo ndihmoi për të bindur portugezët të shkatërronin forcat e sulltanit të mërguar.U bënë një sërë përpjekjesh për të shtypur Malajzët, por vetëm në vitin 1526 portugezët më në fund e rrafshuan Bintanin me tokë.Më pas, sulltani u tërhoq në Kampar në Sumatra dhe vdiq dy vjet më vonë.Ai la pas dy djem të quajtur Muzaffar Shah dhe Alauddin Riayat Shah II.^[53] Muzaffar Shah vazhdoi të themelonte Perakun ndërsa Alauddin Riayat Shah u bë sulltani i parë i Johorit.^[53]