我從未得到過補償。他們不尊重我，我的待遇也與我的身份不符。一顆高貴的心受到嚴重的侮辱、冒犯，以及不公正的對待……他們認為無需按照法律對待我們，特別是考慮到我的臣民只不過是卡菲爾人，他們更是如此。
——蒙巴薩蘇丹優素福寄至果阿的一封信，1637年
為了奪取對蒙巴薩的控制權，該城所遭受的苦難已使人幾乎無法再探尋到它之前的繁榮景象。蘇丹及其3個兒子晦澀不明的死亡造成了徹底的權力真空。葡萄牙人此時已經決定要佔領這座島，以填補這個真空，他們帶來「忠誠的」馬林迪蘇丹艾哈邁德，讓他成為該城新的統治者。更可怖的土耳其人入侵的可能性是刺激他們做出這個決定的主要原因，因為有報告稱，他們在埃及正制訂計劃，要開通一條運河以連線紅海北端和尼羅河，通過這條運河，奧斯曼人的戰艦就能從地中海直接航行到印度洋。
1586年，法國駐君士坦丁堡的大使薩瓦里·德·蘭斯科斯梅派人到巴黎彙報，10萬名工匠、4萬頭驢和1.2萬頭駱駝將用來開鑿這條運河。一旦運河建好，200艘全副武裝的船隻將從那裡通過，他們會把葡萄牙人趕回到好望角的另一邊。一位不知姓名的土耳其人寫了《通往印度的西部路線》（citethewesternroutetoindia/cite）一書，他滿懷樂觀地寫到這條運河建成之後，「邪惡的無信仰者」就會從辛吉海被驅逐出去，之後，君士坦丁堡可以更容易享有「信德和印度的精美貨物，以及衣索比亞（非洲）的珍寶」。
關於土耳其人的這些計劃的報告到達里斯本幾年後，葡萄牙人終於開始在蒙巴薩建造一座要塞。它必須是一座堅固到能夠控制東非海岸的堡壘，而且必須能夠對抗敵人可能施以的任何進攻。它將被稱作耶穌堡。所有在東非做貿易的船隻都要上繳百分之六的海關關稅，這筆錢能夠抵償建造要塞的成本，並且可以支付它的維修費用。
耶穌堡註定成為葡萄牙帝國短暫輝煌的不可摧毀的紀念碑。但是，下令建造它的人是一個西班牙人，而它的建築師則是一位義大利人。那個西班牙人就是在阿維什王朝衰落之際於1580年獲得葡萄牙王位的腓力二世。
腓力二世有很多寵臣，其中一個是喬瓦尼·巴蒂斯塔·卡伊拉蒂，他是米蘭人，年輕時就被派去指導防備土耳其人圍攻的馬耳他防禦工事的建造。卡伊拉蒂作為一個軍事建築師的聲譽傳遍南歐，到16世紀70年代，他在西班牙效命於腓力二世。
在伊比利亞國家不幸地聯合後不久，卡伊拉蒂的皇家保護人就派他作為葡萄牙在東方所有防禦工事的總建築師。50歲左右，他去果阿赴任，之後卡伊拉蒂就將他的西班牙名字改成與之相當的葡萄牙名字——若昂·巴蒂斯塔·凱拉託。在他生命的最後十三年，他在印度洋的各個地方，甚至在東邊遠至馬六甲海峽的地方，設計建造堡壘。耶穌堡是他最後也是最偉大的作品，他在設計這座建築時回溯了義大利的藝術源頭。它是從文藝復興全盛時期「完美的人體」理論中獲取靈感的顯著代表。耶穌堡的平面圖非常清楚地說明了這一點：四座稜堡是胳膊和腿，面向大海的外壘是頭部，整個結構的中心區域則是軀幹。而很好地掩映在一座堡壘的火爐後的大門，實際上處於腋下的位置。
卡伊拉蒂使用「人體形態」的理念，不僅是出於對在他年輕時就聞名義大利的哲學觀念的回應。耶穌堡的設計還非常貼合當地的地形，在它遭到圍攻時便於安排人手。在開始建造耶穌堡之前，在從果阿到蒙巴薩的途中，卡伊拉蒂應該已經意識到，由於葡屬印度總是缺少人力，有效的守備部隊的規模會很小（幾乎不會超過100人）。所以，佈局要簡單，只有幾個防禦點，儘可能少地將堡壘內的力量暴露給進攻者。
耶穌堡的規模依然很大，足以保證遭遇長時段圍攻期間的生存條件。它大概有150碼長，兩座放置武器的稜堡之間寬約130碼；中部庭院有將近75碼寬，兵營、儲存室和一個小教堂位於其兩邊，它們由幕牆圍護；有一口深井，可以為駐軍提供飲用水。耶穌堡的指揮官被莊重地授予「蒙巴薩總督」的頭銜，他的房間位於大門上方。
耶穌堡的城牆面向大海，建在珊瑚巖上，旨在威嚇住潛在的敵人。超過12英尺厚、面向珊瑚塊且用碎石填築的牆壁，足以抵禦16世紀末任何海軍槍炮的攻擊。底下是外部防禦工事，它緊鄰大海，通過一個低矮的拱門和一條狹窄的通道，與內部的庭院相連。
卡伊拉蒂一定立刻就意識到，面向島嶼中心的耶穌堡的西端，是入侵者最容易突破的地方。他的解決辦法是遵循義大利軍事建築的最優良傳統。堡壘的兩條短而粗的「腿」在側翼隱藏著炮臺。每個炮臺都可以掃射到稜堡對面後牆的通道。這些設計還包括在堡壘向陸地的一面建造一條壕溝。
耶穌堡在幾年中的建造速度很快。在強有力的蒙巴薩第一任指揮官馬特烏斯·門德斯·德·瓦斯康塞洛斯的帶領下，成批的印度泥瓦匠、採石工、木匠從果阿來到這裡。包括幾艘停在海港裡以防禦再度前來進攻的土耳其人的船隻上的船員在內，所有的勞動力都加入到堡壘的建設中。軍官們也和士兵一起勞動。甚至新任蘇丹也擺出象徵性的姿態，和他的侍臣們來到海邊幫助搬運石頭。
卡伊拉蒂看到大家熱火朝天的勞動景象一定很開心。可能是想要在他返回歐洲的途中拜訪蒙巴薩，因為在東方待了十多年之後，他告訴腓力二世他最熱切的願望是退休後回到米蘭。（他的故鄉米蘭仍然十分熱愛他，他計劃將他一生的大部分積蓄用來擴充套件當地的醫院。）國王告訴他，等找到他的接替者他就可以回去。1596年，卡伊拉蒂在果阿去世，彼時他還在等待他的繼任者。
與在熱帶的葡萄牙帝國的其他地方經常發生的事情一樣，蒙巴薩的精力和金錢很快開始枯竭。在繼任的指揮官浪費和盜取資金的情況下，耶穌堡的建造幾乎陷入停滯狀態。在堡壘開始建造近20年之後，蒙巴薩的葡萄牙商人先驅還會對人抱怨說防禦牆不夠高。還有很多需要完成的事。即便這樣，移民的數量還在穩固地增長，甚至主街上還流傳著一個嘲弄的說法，稱這座堡壘為散兵坑。最後，蒙巴薩聚集了大概70個家庭，再加上他們的奴隸和溜鬚拍馬者。儘管對於他們沒有記錄，但是一些印度店主和工匠也一定從果阿跨海移民至此。他們從阿拉伯商人化作廢墟的建築中搜取石塊建造他們自己的房屋，以及一座奧古斯丁教堂和女修道院。
但是，葡萄牙人並不信任那個和他們一起分享蒙巴薩島的斯瓦希里人，因為他們與蘇丹艾哈邁德的早期情誼很快就消逝了。蘇丹艾哈邁德曾經認為，從馬林迪搬到蒙巴薩會使他成為整個斯瓦希里海岸的大領主，但是實際的權力掌握在耶穌堡緩緩升起的高牆後面。葡萄牙軍官們掌握著權力，而蒙巴薩的蘇丹只能忍耐。蘇丹給里斯本的國王寫信，說沒有必要建造這座堡壘。由於葡萄牙居民在貿易中享有不公平的優惠條件，而歷任指揮官又對他態度輕蔑，他的個人地位正不斷被削弱，但是他的信沒有得到理會。
17世紀，在東方有多年生活經驗的葡萄牙指揮官若昂·羅貝羅，應該很能理解他的最後一個抱怨：「我不懷疑在那些接受派遣管理堡壘的人之中，不乏表現友好的人，但是他們做不好事情，因為一個壞人做錯事要比一百個好人做好事的影響深得多。」
當蘇丹艾哈邁德請求派商船前往中國時，他的自尊再次受到嚴重打擊。他不可能擁有足夠完成1.5萬英里環球航程的遠洋大船，但是他可以在印度輕易地僱用到它們。前往中國的貨船和以往一樣載著象牙、龍涎香、非洲的黃金和稀有的獸皮；返航的船隻則滿載瓷器和絲綢。可能在馬林迪還流傳著將近200年前鄭和船隊造訪的傳說，以及由這座城市送給中國皇帝長頸鹿的事蹟。
蘇丹知道他必須得到葡萄牙人的許可，因為沒有通行證，任何在印度洋航行的船隻都會被劫掠或者炸沉。他曾經確信他可以得到許可，因為他和他的祖輩一直對葡萄牙人表現忠誠，但是他的請求被草率地拒絕了。
1610年，新任蘇丹哈桑就任，而堡壘的新任指揮官是曼努埃爾·德·梅洛·佩雷拉。這兩者之間的敵意很快變得十分強烈，以致於哈桑從蒙巴薩逃往大陸，與一個非洲人社群生活在一起。曼努埃爾·德·梅洛耍手段，在一場伏擊中殺害了蘇丹。葡萄牙人支付了2000段布料，了結了此事。當蘇丹的屍體被送回蒙巴薩時，他的頭被砍下來送給了果阿的總督，附帶的報告說蘇丹只是遭受了他應得的懲罰，因為他犯了叛國罪。
蘇丹的繼承人是7歲男孩優素福，因而蒙巴薩的指揮官就任攝政者，他來自一個反對前任蘇丹的派系。優素福乘船前往印度，在那裡他皈依了基督教，他在果阿的奧古斯丁修會會士處接受教育，然後乘坐葡萄牙船隻學習航海技術和戰爭藝術。到他十八九歲時，他的名字從優素福改為熱羅尼莫。他的導師們認為他已經可以繼承蘇丹之位。他在果阿加冕，被授予「蒙巴薩、馬林迪和奔巴島之王」的頭銜，成為基督騎士團的一名騎士，並在1626年的盛大儀式中被送回故鄉。跟他一起出發的有一位奧古斯丁修會會士，還有他來自果阿、名叫伊莎貝爾的妻子。