W 1511 roku Malakka padła w ręce Portugalczyków , a sułtan Mahmud Shah został zmuszony do ucieczki z Malakki.Sułtan kilkakrotnie próbował odzyskać stolicę, ale jego wysiłki były bezowocne.Portugalczycy zemścili się i zmusili sułtana do ucieczki do Pahang.Później sułtan popłynął do Bintan i założył tam nową stolicę.Po utworzeniu bazy sułtan zebrał rozproszone siły malajskie i zorganizował kilka ataków i blokad na pozycję Portugalii.Sułtanat Johor z siedzibą w Pekan Tua, Sungai Telur, Johor, został założony przez Raja Ali Ibni Sultan Mahmud Melaka, znany jako sułtan Alauddin Riayat Shah II (1528–1564), w 1528 r. ^[53] Chociaż sułtan Alauddin Riayat Shah i jego następca musieli stawić czoła atakom Portugalczyków w Malakce i Acehnese na Sumatrze, udało im się utrzymać kontrolę nad sułtanatem Johor.Częste naloty na Malakkę sprawiły Portugalczykom poważne trudności i pomogły przekonać Portugalczyków do zniszczenia sił wygnanego sułtana.Podjęto szereg prób stłumienia Malajów, ale dopiero w 1526 roku Portugalczycy ostatecznie zrównali Bintan z ziemią.Następnie sułtan wycofał się do Kampar na Sumatrze i zmarł dwa lata później.Pozostawił dwóch synów o imieniu Muzaffar Shah i Alauddin Riayat Shah II.^[53] Muzaffar Shah kontynuował zakładanie Peraka, podczas gdy Alauddin Riayat Shah został pierwszym sułtanem Johor.^[53]