I 1511 falt Malacca for portugiserne og sultan Mahmud Shah ble tvunget til å flykte fra Malacca.Sultanen gjorde flere forsøk på å gjenerobre hovedstaden, men hans innsats var resultatløs.Portugiserne tok igjen og tvang sultanen til å flykte til Pahang.Senere seilte sultanen til Bintan og etablerte en ny hovedstad der.Med en base etablert, samlet sultanen de oppløste malaysiske styrkene og organiserte flere angrep og blokader mot den portugisiske posisjonen.Med base i Pekan Tua, Sungai Telur, Johor, ble Johor-sultanatet grunnlagt av Raja Ali Ibni Sultan Mahmud Melaka, kjent som Sultan Alauddin Riayat Shah II (1528–1564), i 1528. ^[53] Selv om Sultan Alauddin Riayat Shah og hans etterfølger måtte kjempe med angrep fra portugiserne i Malacca og fra acehneserne på Sumatra, klarte de å opprettholde grepet om Johor-sultanatet.Hyppige raid på Malacca forårsaket portugiserne alvorlig motgang, og det bidro til å overbevise portugiserne om å ødelegge den eksilerte sultanens styrker.Det ble gjort en rekke forsøk på å undertrykke malayerne, men det var ikke før i 1526 at portugiserne til slutt jevnet Bintan med jorden.Sultanen trakk seg deretter tilbake til Kampar på Sumatra og døde to år senere.Han etterlot seg to sønner ved navn Muzaffar Shah og Alauddin Riayat Shah II.^[53] Muzaffar Shah fortsatte å etablere Perak mens Alauddin Riayat Shah ble den første sultanen av Johor.^[53]