Năm 1511, Malacca rơi vào tay người Bồ Đào Nha và Sultan Mahmud Shah buộc phải chạy trốn khỏi Malacca.Quốc vương đã nhiều lần cố gắng chiếm lại thủ đô nhưng những nỗ lực của ông đều không có kết quả.Người Bồ Đào Nha trả đũa và buộc quốc vương phải chạy trốn đến Pahang.Sau đó, nhà vua đi thuyền đến Bintan và thành lập thủ đô mới ở đó.Với một căn cứ đã được thiết lập, quốc vương đã tập hợp các lực lượng Mã Lai đang bị xáo trộn và tổ chức một số cuộc tấn công và phong tỏa nhằm vào vị trí của Bồ Đào Nha.Có trụ sở tại Pekan Tua, Sungai Telur, Johor, Vương quốc Johor được thành lập bởi Raja Ali Ibni Sultan Mahmud Melaka, còn gọi là Sultan Alauddin Riayat Shah II (1528–1564), vào năm 1528. ^[53] Mặc dù Sultan Alauddin Riayat Shah và người kế vị ông phải đối mặt với các cuộc tấn công của người Bồ Đào Nha ở Malacca và người Aceh ở Sumatra, họ vẫn cố gắng duy trì quyền kiểm soát Vương quốc Johor.Các cuộc đột kích thường xuyên vào Malacca đã khiến người Bồ Đào Nha gặp khó khăn nghiêm trọng và nó giúp thuyết phục người Bồ Đào Nha tiêu diệt lực lượng của vị vua lưu vong.Một số nỗ lực đã được thực hiện để đàn áp người Mã Lai nhưng phải đến năm 1526, người Bồ Đào Nha cuối cùng mới san bằng Bintan.Sau đó, quốc vương rút lui về Kampar ở Sumatra và qua đời hai năm sau đó.Ông để lại hai người con trai tên là Muzaffar Shah và Alauddin Riayat Shah II.^[53] Muzaffar Shah tiếp tục thành lập Perak trong khi Alauddin Riayat Shah trở thành quốc vương đầu tiên của Johor.^[53]