1511'de Malakka Portekizlilerin eline geçti ve Sultan Mahmud Şah Malakka'dan kaçmak zorunda kaldı.Sultan, başkenti geri almak için birçok girişimde bulundu ancak çabaları sonuçsuz kaldı.Portekizliler misilleme yaptı ve padişahı Pahang'a kaçmaya zorladı.Daha sonra padişah Bintan'a doğru yola çıktı ve orada yeni bir başkent kurdu.Kurulan bir üs ile padişah, dağınık Malay güçlerini topladı ve Portekiz'in pozisyonuna karşı çeşitli saldırılar ve ablukalar düzenledi.Pekan Tua, Sungai Telur, Johor merkezli Johor Sultanlığı, 1528'de Sultan Alauddin Riayat Şah II (1528-1564) olarak bilinen Raja Ali İbni Sultan Mahmud Melaka tarafından kuruldu ^[.53] Her ne kadar Sultan Alauddin Riayat Şah ve halefi Malakka'da Portekizlilerin ve Sumatra'da Acehnese'nin saldırılarıyla mücadele etmek zorunda kaldılar ve Johor Sultanlığı üzerindeki hakimiyetlerini korumayı başardılar.Malakka'ya sık sık yapılan baskınlar Portekizlilere ciddi zorluklar yaşattı ve Portekizlileri sürgündeki padişahın güçlerini yok etmeye ikna etmeye yardımcı oldu.Malayları bastırmak için bir dizi girişimde bulunuldu, ancak Portekizlilerin Bintan'ı yerle bir etmesi ancak 1526 yılına kadar mümkün oldu.Sultan daha sonra Sumatra'daki Kampar'a çekildi ve iki yıl sonra öldü.Geride Muzaffar Şah ve Alauddin Riayat Şah II adında iki oğlu bıraktı.^[53] Muzaffar Şah Perak'ı kurmaya devam ederken Alauddin Riayat Şah Johor'un ilk padişahı oldu.^[53]