After the fall of Malacca, Sultan Mahmud Shah attempted repeatedly to recapture his capital from the Portuguese. Each assault failed. The Portuguese retaliated, forcing the sultan to flee to Pahang and then onward to the island of Bintan, where he established a temporary base. From Bintan, the sultan rallied the scattered Malay forces and organized raids and naval blockades against Portuguese Malacca -- attacks persistent enough to cause the colonizers genuine hardship. But the Portuguese eventually destroyed Bintan in 1526, and the sultan died shortly after. His son Alauddin Riayat Shah II picked up the cause, founding a new capital by the Johor River in 1528. From there, he continued to harass the Portuguese while building alliances with his brother in Perak and the Sultan of Pahang, aiming always at the recapture of Malacca and its fortress, A Famosa.

The struggle for the Strait of Malacca was never a simple contest between two powers. By the mid-sixteenth century, three rivals competed for dominance: the Portuguese holding Malacca, the Johor Sultanate pressing from the south, and the rising Aceh Sultanate pushing from northern Sumatra. With Malacca in Christian hands, Muslim traders increasingly bypassed it in favor of Aceh or Johor's capital at Johor Lama. This triangular war reshaped the entire region. Aceh attacked both Malacca and Johor, sacking Johor Lama in 1564 and again in later campaigns. The Portuguese defended their fortress but could not project power far beyond its walls. Johor, caught between two enemies, survived through diplomacy, naval mobility, and the strategic advantage of controlling the islands and river systems of the southern strait.

When Dutch traders reached Southeast Asia in the early seventeenth century, they found a ready ally in Johor. Both shared an enemy in Portugal. In 1606, Admiral Cornelis Matelief de Jonge signed two treaties with Raja Bongsu of Johor -- agreements that would reshape the region's power dynamics for the next two centuries. The alliance bore fruit in January 1641 when Dutch and Johor forces, the latter commanded by Bendahara Skudai, captured Malacca from the Portuguese. By the time the fortress surrendered, famine and plague had already devastated the town's population. The victory was pyrrhic in some respects: the Dutch had no intention of sharing power equally, and Johor soon discovered that replacing one European overlord with another brought its own complications.

With Portuguese Malacca gone and Aceh declining under Dutch pressure, Sultan Abdul Jalil Shah III rebuilt Johor's influence during his reign from 1623 to 1677. The sultanate's reach extended across Pahang, Sungei Ujong, Malacca, Klang, and the Riau Archipelago. But a new rival emerged: the Jambi Sultanate in Sumatra, which had grown into a regional economic and political power during the decades of triangular conflict. An attempted alliance through marriage collapsed, and the two sultanates went to war. The Johor-Jambi wars consumed resources and attention at precisely the moment when the Dutch and British were tightening their grip on Southeast Asian trade. Internal palace rivalries compounded the external pressures, weakening the sultanate from within.

In 1818, Sir Stamford Raffles arrived in Bencoolen on Sumatra's west coast, convinced that Britain needed a new base in Southeast Asia to counter Dutch influence. When his expedition reached Singapore on 29 January 1819, he found a small Malay settlement and a succession dispute he could exploit. The Johor Sultanate had fractured: one claimant was recognized by the Dutch, another waited in the wings. Raffles backed the overlooked claimant, Hussein Shah, installed him as sultan, and secured a treaty granting Britain control of Singapore. The maneuvering effectively split the sultanate between British and Dutch spheres of influence. By 1855, what had been a single maritime empire stretching from the Malay Peninsula to the Riau Islands and Sumatra had been carved into colonial possessions, its centuries of sovereignty dissolved in European ink.