Im Jahr 1511 fiel Malakka an die Portugiesen und Sultan Mahmud Schah musste aus Malakka fliehen.Der Sultan unternahm mehrere Versuche, die Hauptstadt zurückzuerobern, doch seine Bemühungen blieben erfolglos.Die Portugiesen revanchierten sich und zwangen den Sultan zur Flucht nach Pahang.Später segelte der Sultan nach Bintan und gründete dort eine neue Hauptstadt.Nachdem er einen Stützpunkt errichtet hatte, versammelte der Sultan die verwirrten malaiischen Streitkräfte und organisierte mehrere Angriffe und Blockaden gegen die portugiesische Position.Das Johor-Sultanat mit Sitz in Pekan Tua, Sungai Telur, Johor, wurde 1528 von Raja Ali Ibni Sultan Mahmud Melaka, bekannt als Sultan Alauddin Riayat Shah II (1528–1564), gegründet. ^[53] Obwohl Sultan Alauddin Riayat Shah und sein Nachfolger Während sie mit Angriffen der Portugiesen in Malakka und der Acehnesen in Sumatra zu kämpfen hatten, gelang es ihnen, das Johor-Sultanat zu behaupten.Häufige Überfälle auf Malakka bereiteten den Portugiesen große Schwierigkeiten und trugen dazu bei, die Portugiesen davon zu überzeugen, die Streitkräfte des verbannten Sultans zu vernichten.Es wurden mehrere Versuche unternommen, die Malaien zu unterdrücken, aber erst 1526 machten die Portugiesen Bintan endgültig dem Erdboden gleich.Anschließend zog sich der Sultan nach Kampar auf Sumatra zurück und starb zwei Jahre später.Er hinterließ zwei Söhne namens Muzaffar Shah und Alauddin Riayat Shah II.^[53] Muzaffar Shah baute Perak weiter auf, während Alauddin Riayat Shah der erste Sultan von Johor wurde.^[53]