Pada tahun 1511, Malaka jatuh ke tangan Portugis dan Sultan Mahmud Syah terpaksa meninggalkan Malaka.Sultan melakukan beberapa upaya untuk merebut kembali ibu kota namun usahanya tidak membuahkan hasil.Portugis membalas dan memaksa sultan melarikan diri ke Pahang.Kemudian sultan berlayar ke Bintan dan mendirikan ibu kota baru di sana.Dengan didirikannya basis, sultan mengumpulkan kekuatan Melayu yang tercerai-berai dan mengorganisir beberapa serangan dan blokade terhadap posisi Portugis.Berbasis di Pekan Tua, Sungai Telur, Johor, Kesultanan Johor didirikan oleh Raja Ali Ibni Sultan Mahmud Melaka, yang dikenal sebagai Sultan Alauddin Riayat Shah II (1528–1564), pada tahun 1528. ^[53] Meskipun Sultan Alauddin Riayat Shah dan penerusnya harus menghadapi serangan Portugis di Malaka dan serangan Aceh di Sumatera, mereka berhasil mempertahankan kekuasaannya di Kesultanan Johor.Penggerebekan yang sering terjadi di Malaka menyebabkan kesulitan besar bagi Portugis dan membantu meyakinkan Portugis untuk menghancurkan pasukan sultan yang diasingkan.Sejumlah upaya dilakukan untuk menekan Melayu namun baru pada tahun 1526 Portugis akhirnya merobohkan Bintan hingga rata dengan tanah.Sultan kemudian mundur ke Kampar di Sumatra dan meninggal dua tahun kemudian.Ia meninggalkan dua orang putra bernama Muzaffar Shah dan Alauddin Riayat Shah II.^[53] Muzaffar Shah terus mendirikan Perak sementara Alauddin Riayat Shah menjadi sultan pertama Johor.^[53]