I 1511 faldt Malacca til portugiserne og sultan Mahmud Shah blev tvunget til at flygte fra Malacca.Sultanen gjorde flere forsøg på at generobre hovedstaden, men hans bestræbelser var frugtesløse.Portugiserne gjorde gengæld og tvang sultanen til at flygte til Pahang.Senere sejlede sultanen til Bintan og etablerede en ny hovedstad der.Med en base etableret samlede sultanen de uordentlige malaysiske styrker og organiserede adskillige angreb og blokader mod den portugisiske position.Baseret på Pekan Tua, Sungai Telur, Johor, blev Johor Sultanatet grundlagt af Raja Ali Ibni Sultan Mahmud Melaka, kendt som Sultan Alauddin Riayat Shah II (1528-1564), i 1528. ^[53] Selvom Sultan Alauddin Riayat Shah og hans efterfølger måtte kæmpe med angreb fra portugiserne i Malacca og fra acehnerne på Sumatra, formåede de at bevare deres greb om Johor-sultanatet.Hyppige razziaer på Malacca forårsagede portugiserne alvorlige nød, og det var med til at overbevise portugiserne om at ødelægge den eksilerede sultans styrker.Der blev gjort en række forsøg på at undertrykke malayerne, men det var først i 1526, at portugiserne endelig jævnede Bintan med jorden.Sultanen trak sig derefter tilbage til Kampar på Sumatra og døde to år senere.Han efterlod sig to sønner ved navn Muzaffar Shah og Alauddin Riayat Shah II.^[53] Muzaffar Shah fortsatte med at etablere Perak, mens Alauddin Riayat Shah blev den første sultan af Johor.^[53]