Pêro da Covilhã, a Portuguese explorer and spy traveling overland disguised as an Arab merchant, had been the first European known to have visited Sofala in 1489.

His secret report to Lisbon had identified Sofala's role as a gold emporium (although by this time, the gold trade was quite diminished from its heyday).

In 1501, Sofala had been scouted from the sea and its location determined by captain Sancho de Tovar.

In 1502, Pedro Afonso de Aguiar (others say Vasco da Gama himself) led the first Portuguese ships into Sofala harbor.

Aguiar (or Gama) had sought out an audience with the ruling sheikh Isuf of Sofala (Yçuf in João de Barros’ Çufe in Damião de Goes).

At the time, Isuf was engaged in a quarrel with Kilwa.

The minister Emir Ibrahim had deposed and murdered the legitimate Sultan al-Fudail of Kilwa, and seized power for himself.

Isuf of Sofala had refused to recognize the usurper and was looking for a way to shake off Kilwa's lordship and chart an independent course for Sofala.

The Portuguese, with their powerful ships, seemed to provide the key.

At any rate, the elderly sheikh Isuf realized it would be better to make allies rather than enemies out of them, and had agreed to a commercial and alliance treaty with the Kingdom of Portugal.

This is followed upon in 1505 when Pêro de Anaia (part of the Seventh Portuguese Armada) is granted permission by Sheikh Isuf to erect a factory and fortress near the city.

Fort São Caetano of Sofala is the second Portuguese fort in East Africa (the first, at Kilwa, had been built only a few months earlier).

Anaia uses stone imported for the purpose from Europe.

(It will subsequently be reused for construction of Beira's cathedral.)

The Portuguese fort does not last very long, as much of the garrison is quickly decimated by fevers (probably malaria).