At the end of the 15th century, the Spanish and Portuguese Crowns started to partition the world. The spice commerce with the Indies was a very coveted bite, still under the control of the Turkish Empire.

In November 1497, the Portuguese navigator Vasco da Gama (1460-1524), commissioned by king Manuel I the Fortunate to open the route to the Indies, was the first European to sail round the Cape of Good Hope. The Portuguese arrived in Mombasa on the 7th of April 1498, where the Arabs repelled them cutting their anchors. The expedition went on northward and docked at Malindi one week later. The sailor came to terms with the local sultan, who supplied a pilot that knew the route to Calicut (Kozhikode), the most important commercial port in Southwest India at the time.

The expedition weighed anchor and reached the coast of Calicut on May the 20th, opening up the route of the Indies for the Portuguese Crown. Nonetheless, the navigator was unsuccessful in this first commercial operation: in addition to hostility from Muslim traders, the Zamorin (Hindu ruler of Calicut) failed to appreciate the goods brought by the Portuguese, suitable for trading in West Africa but scarcely demanded in India.

Tension increased and Vasco da Gama was bound to leave Calicut, and after a long and tough trip during which scurvy decimated the crew, the expedition arrived back in Malindi on the 8th of January 1499, where da Gama ordered to burn his vessel San Rafael, since the available crew was insufficient.

The strategic importance of the East African harbours prompted the Portuguese Crown to seize this region. For ten years, the Portuguese Navy sieged and conquered all the coastal cities save their ally Malindi. Mombasa gained its reputation of rebel city since it resisted invasion, being destroyed three times, in 1502, 1528 and finally in 1588, when it finally fell under Portuguese control. The new metropolis modified the commercial routes in the Indian Ocean, detouring the Sofala gold round the Cape of Good Hope towards Europe.

The presence of Portugal in the East African coast was lasting. Nonetheless, there was never an actual colonization, since the influence did not extend beyond the military positions. The Portuguese heritage was limited to new crops imported from South America such as corn, manioc, cashew, tomato and tobacco, in addition to some Portuguese words that yet survive in the Swahili language.

The new situation did not quieten the wishes of Muslims to recover their former domination of the region. The Turkish Empire, splendidly flourishing after conquering Egypt and Arabia, sent Ali Bey to Mombasa to uprise the Arabs of the Coast against the Christians. The visit was repeated in 1588 with five vessels. Mombasa opened its gates for the Turks, who established their headquarters in the island. The Portuguese, fearing a revolt, sent reinforcements from Goa, in India. The Portuguese fleet arrived in Mombasa in 1590, and so did the Zimba, a cannibal tribe from the Zambezi region that was raiding the coast and spreading horror. The Portuguese allied with the Zimba and devastated the city, leaving it later to the cannibals.

Fearing further attacks from the Turks, in 1593 the Portuguese decided to build a fortress in Mombasa, Fort Jesus, where they seated their military headquarters and moved their ally, the ruler of Malindi, who was appointed as the new sultan of Mombasa. But relationships were not straightforward. The sultan was murdered in 1626 on behalf of the Portuguese captain and was succeeded by his son, don Jeronimo, who revolted against the Europeans in 1631 and exterminated all the Portuguese who had sheltered inside the fortress, except for five survivors. The Arab presence grew from then on and Mombasa met a new period of splendour.

Meanwhile, a new power was emerging in the Indian Ocean: Oman. The Omanis, established in Muscat after throwing the Portuguese away in 1650, built relationships with the East African harbours until the sultan of Oman resolved to conquer the region. On the 11th of March 1696, seven Omani ships, along with an army of 3,000 soldiers, entered the port of Mombasa. The Portuguese, who were aware of the operation, had gathered 2,500 men in Fort Jesus. So started a long siege during which the entrenched in the fortress were decimated by the bubonic plague. At the end of the year, only 50 Portuguese survived. Still, somehow they managed to extend their resistance for nearly two more years, until they received reinforcements in September 1698. In December the same year new reinforcements arrived in Mombasa, but it was too late: on December the 13th, the sultan of Oman was informed that only 20 survived inside the fort, of which only 8 were soldiers. The final attack was triggered, and after a 33 month siege, Fort Jesus finally fell in Oman's hands.

Years later, in 1728, Portugal would make one last and desperate attempt to recover Mombasa. The failure put an everlasting end to the Portuguese presence in the East African coast.