In the early 17th century, the Dutch East India Company (Verenigde Oostindische Compagnie, VOC) began the campaign to destroy Portuguese power in the East. At that time, the Portuguese had transformed Malacca into an impregnable fortress (the Fortaleza de Malaca), controlling access to the sea lanes of the Straits of Malacca and the spice trade there. The Dutch started by launching small incursions and skirmishes against the Portuguese. The first serious attempt was the siege of Malacca in 1606 by the third VOC fleet from Holland with eleven ships, led by Admiral Cornelis Matelief de Jonge that lead to the naval battle of Cape Rachado. Although the Dutch were routed, the Portuguese fleet of Martim Afonso de Castro, the Viceroy of Portuguese India; suffered heavier casualties and the battle rallied the forces of the Sultanate of Johor in an alliance with the Dutch and later on with the Achehnese.
The Dutch with their local allies assaulted and wrestled Malacca from the Portuguese in January 1641. This combined Dutch-Johor-Acheh efforts effectively destroyed the last bastion of Portuguese power, removing their influence in the Malay archipelago. As per the agreement with Johor in 1606, the Dutch took control of Malacca and agreed not to seek territories or wage war with the Malay kingdoms.