Το 1511, η Μαλάκα έπεσε στα χέρια των Πορτογάλων και ο Σουλτάνος ​​Μαχμούντ Σαχ αναγκάστηκε να φύγει από τη Μαλάκα.Ο σουλτάνος ​​έκανε πολλές προσπάθειες να ανακαταλάβει την πρωτεύουσα αλλά οι προσπάθειές του απέβησαν άκαρπες.Οι Πορτογάλοι αντεπιτέθηκαν και ανάγκασαν τον σουλτάνο να καταφύγει στο Pahang.Αργότερα, ο σουλτάνος ​​έπλευσε στο Μπιντάν και ίδρυσε εκεί μια νέα πρωτεύουσα.Με τη δημιουργία μιας βάσης, ο σουλτάνος ​​συγκέντρωσε τις διαταραγμένες δυνάμεις της Μαλαισίας και οργάνωσε αρκετές επιθέσεις και αποκλεισμούς κατά της πορτογαλικής θέσης.Με έδρα το Pekan Tua, Sungai Telur, Johor, το σουλτανάτο Johor ιδρύθηκε από τον Raja Ali Ibni Sultan Mahmud Melaka, γνωστό ως Sultan Alauddin Riayat Shah II (1528–1564), το 1528. ^[53] Αν και ο σουλτάνος ​​Alauddin Riayat Shah και ο διάδοχός του έπρεπε να αντιμετωπίσουν τις επιθέσεις των Πορτογάλων στη Malacca και των Acehnese στη Σουμάτρα, κατάφεραν να διατηρήσουν την κυριαρχία τους στο σουλτανάτο Johor.Οι συχνές επιδρομές στη Μαλάκα προκάλεσαν σοβαρές δυσκολίες στους Πορτογάλους και βοήθησαν να πειστούν οι Πορτογάλοι να καταστρέψουν τις δυνάμεις του εξόριστου σουλτάνου.Έγιναν πολλές προσπάθειες για να καταστείλουν τους Μαλαισιανούς, αλλά μόνο το 1526 οι Πορτογάλοι ισοπέδωσαν τελικά τον Μπιντάν.Στη συνέχεια, ο σουλτάνος ​​υποχώρησε στο Kampar στη Σουμάτρα και πέθανε δύο χρόνια αργότερα.Άφησε πίσω του δύο γιους, τους Muzaffar Shah και Alauddin Riayat Shah II.^[53] Ο Muzaffar Shah συνέχισε να ιδρύει το Perak ενώ ο Alauddin Riayat Shah έγινε ο πρώτος σουλτάνος ​​του Johor.^[53]