The Turkish raids of 1585 and 1588 were decisive for the Portuguese to decide the construction of the fort in Mombasa. On 11 April 1593 the fortress was dedicated and named "Fortaleza de Jesus de Mombaça" by Mateus de Mendes de Vasconcelos (he was the captain of the coast, that resided at Malindi). The fort was completed in 1596, the plan was a quadrilater with four bastions: S. Felipe, S. Alberto, S. Mathias and S. Mateus. The main gate was near S. Mathias bastion. Above the gate is a Portuguese inscription that records the dedication to the fort: "Reinando em Portugal Phellipe de Austria o primeiro ... por seu mandado ....... fortaleza de nome Jesus de Mombaca aomze dabril de 1593 ..... Visso Rei da India Mathias Dalboquerque ....... Matheus Mendes de Vasconcellos que pasou com armada e este porto ....... arquitecto mor da India Joao Bautista Cairato servindo de mestre das obras Gaspar Rodrigues."
Fort Jesus, located on the edge of a coral ridge overlooking the entrance to the Old Port of Mombasa, was built by the Portuguese in 1593-1596 to protect their trade route to India and their interests in East Africa. It was designed by an Italian architect, Giovanni Battista Cairati*. Mombasa became Portugal's main trading centre along the East Coast of Africa.
Relation between the Portuguese and the Sultan of Mombasa began to deteriorate after the departure of the first captain Mateus de Mendes de Vasconcelos. In 1626, Muhammad Yusif, who had received education in Goa and that was baptized as Dom Jeronimo Chingulia, was made Sultan. On 16 August 1631, the Sultan Dom Jeronimo Chingulia entered the fort and took the Portuguese by surprise, he killed the Portuguese captain, Pedro Leitão de Gamboa, and massacred the whole Portuguese population of Mombasa (45 men, 35 women and 70 children). A Portuguese expedition was send from Goa to retake the fort, but after two months of siege (10 January 1632-19 March 1632) they abandoned the enterprise. On 16 May the Sultan abandoned Mombasa and became a pirate. On 5 August 1632 a small Portuguese force under the captain Pedro Rodrigues Botelho, that had remained at Zanzibar, reoccupied the fort.
In February 1661 the Sultan of Oman sacked the Portuguese town of Mombasa but did not attack the fort. It was in 1696 that a large Omani Arabs expedition reached Mombasa, from 13 March 1696 the fort was under siege, the fort had a garrison of 50-70 Portuguese soldiers and several hundred loyal coast Arabs. The fort was relieved in December 1696 by a Portuguese expedition, but in the following months a plague killed all the Portuguese of the garrison and by 16 June 1697 the defence of the fort was in the hand of Sheikh Daud of Faza with 17 of his family, 8 African men and 50 African women. On 15 September 1697 a Portuguese ship arrived with some reinforcement and also at the end of December 1697 another ship came from Goa with a few soldiers. After another year of siege, in December 1698, the Portuguese garrison was reduced to the Captain, 9 men and a priest (Fr. Manoes de Jesus). After a siege of two years and nine months the Omani Arabs took the fort. They could do this because the garrison was reduced to nine soldiers the others were death by disease. On the morning of 13 December 1698 the Omani Arabs did the decisive attack and took the fort, just seven days later a Portuguese relief fleet arrived at Mombasa, but it was too late. With the conquest of Fort Jesus the whole coast of Kenya and Tanzania with Zanzibar and Pemba fell to the Omani Arabs.
The Portuguese retook the fort in 1728, because the African soldiers in the fort mutined against the Omanits, the Sultan of Pate to which was offered the fort handed the fort over to the Portuguese on 16 March 1728. In April 1729, the Mombasans revolted against the Portuguese and put under siege the garrison that was forced to surrender on 26 November 1729.