År 1511 föll Malacka till portugiserna och sultan Mahmud Shah tvingades fly från Malacka.Sultanen gjorde flera försök att återta huvudstaden men hans ansträngningar var fruktlösa.Portugiserna hämnades och tvingade sultanen att fly till Pahang.Senare seglade sultanen till Bintan och etablerade en ny huvudstad där.Med en bas etablerad samlade sultanen de stökiga malaysiska styrkorna och organiserade flera attacker och blockader mot den portugisiska positionen.Baserat på Pekan Tua, Sungai Telur, Johor, grundades Johor-sultanatet av Raja Ali Ibni Sultan Mahmud Melaka, känd som Sultan Alauddin Riayat Shah II (1528–1564), 1528. ^[53] Även om Sultan Alauddin Riayat Shah och hans efterträdare var tvungna att kämpa med angrepp av portugiserna i Malacka och av acehneserna på Sumatra, lyckades de behålla sitt grepp om Johor-sultanatet.Frekventa räder på Malacka orsakade portugiserna svåra svårigheter och det hjälpte till att övertyga portugiserna att förstöra den exil-sultanens styrkor.Ett antal försök gjordes för att undertrycka malajerna men det var inte förrän 1526 som portugiserna slutligen jämnade Bintan med marken.Sultanen drog sig sedan tillbaka till Kampar på Sumatra och dog två år senare.Han lämnade efter sig två söner vid namn Muzaffar Shah och Alauddin Riayat Shah II.^[53] Muzaffar Shah fortsatte att etablera Perak medan Alauddin Riayat Shah blev den första sultanen av Johor.^[53]