In 1511, Malacca fell to the Portuguese and Sultan Mahmud Shah was forced to flee Malacca. The sultan made several attempts to retake the capital but his efforts were fruitless. The Portuguese retaliated and forced the sultan to flee to Pahang. Later, the sultan sailed to Bintan and established a new capital there. With a base established, the sultan rallied the disarrayed Malay forces and organised several attacks and blockades against the Portuguese position.

Based at Pekan Tua, Sungai Telur, Johor, the Johor Sultanate was founded by Raja Ali Ibni Sultan Mahmud Melaka, known as Sultan Alauddin Riayat Shah II (1528–1564), in 1528.^[53] Although Sultan Alauddin Riayat Shah and his successor had to contend with attacks by the Portuguese in Malacca and by the Acehnese in Sumatra, they managed to maintain their hold on the Johor Sultanate.

Frequent raids on Malacca caused the Portuguese severe hardship and it helped to convince the Portuguese to destroy the exiled sultan's forces. A number of attempts were made to suppress the Malay but it was not until 1526 that the Portuguese finally razed Bintan to the ground. The sultan then retreated to Kampar in Sumatra and died two years later. He left behind two sons named Muzaffar Shah and Alauddin Riayat Shah II.^[53] Muzaffar Shah continued on to establish Perak while Alauddin Riayat Shah became the first sultan of Johor.^[53]