In 1498, a direct sea route was established between India and Portugal. Over time, the Portuguese discovered the affable relationship between the Sultan of Calicut and Sultan Mahmud Shah of Melaka. At the time, Melaka's port was frequented by a multitude of ships and merchants from all over Asia, mostly, Arabia, Persia, China, India, Japan, Ceylon, Bengal and the Indonesian archipelago.

Almost immediately, Alfonso de Albuquerque ordered the construction of a massive fortress south of the river. Today, the remains of the structure popularly known as A'Famosa is synonymous with Melaka's history. The Portuguese ruled Melaka for the next 130 years till the arrival of the Dutch in 1641.