你要在苏伊士为一场圣战做好准备，使舰队配备好武器、装满补给品……你将阻止葡萄牙异教徒的邪恶行径，将他们的旗帜从海洋上移除。
——苏莱曼苏丹致信苏莱曼帕夏，1538年
从他们在东非的少数几个战略要地出发，葡萄牙人向北朝着红海的入口继续紧张地搜寻。尽管由于几十年前阿尔梅达在第乌取得了胜利，奥斯曼土耳其人已被驱逐出印度洋，但是之后他们在埃及获得的胜利使得他们对亚丁和索马里可以施加更大的影响。如果他们派出一支舰队沿着非洲海岸向南航行，他们最有可能的目标是占领蒙巴萨，夺取它优良的天然海港。而且，自从瓦斯科·达·伽马第一次拜访那里之后，当地居民就对葡萄牙人表现出持续的敌意。如果土耳其人占领了蒙巴萨，在果阿和好望角之间航行的所有船只都会处于危险之中。
但是，葡萄牙人不愿亲自去占领蒙巴萨，因为他们缺少能守住那里的人力。其他几个港口也可以作为非洲的黄金、象牙和奴隶等主要出口商品的输出之处，而且由于莫桑比克和马林迪是过往船只所需淡水和补给的中转站，就像罗马对待迦太基那样，直接消灭蒙巴萨是一个诱人的解决方案。
1528—1529年，新任命的葡属印度总督努诺·达·库尼亚被迫在东非度过6个月，在此期间他曾尝试摧毁蒙巴萨。大西洋糟糕的天气严重延误了他的舰队绕过好望角的时间，以致于这支舰队没能赶上可以将他们带往果阿的西南季风。由于丧失了旗舰和其他几艘船，达·库尼亚和他的人意志消沉，只要一想到要在第二年初东北季风停歇之后才能结束在非洲海域的游荡，他们就觉得十分苦楚。连续几个月受阻于马林迪外部的珊瑚礁，这种状况还将持续下去，他们简直无法忍受，因此达·库尼亚决定强行解决蒙巴萨问题。他提前派信使告诉对方，他的船只要直接驶入主港，并且在那里抛锚。
他们的行为令蒙巴萨的苏丹不悦并且警醒。这座城市对23年前阿尔梅达的舰队带来的浩劫和毁坏仍然记忆犹新。苏丹寻求妥协，同意给他们提供食物和水，但是坚持只有派来取这些供给品的人才能上岸。
这对葡萄牙人而言不够理想。达·库尼亚率领下的1500名水手和士兵已经在拥挤污秽的船上度过了漫长的6个月，他们此时极度渴望踏上坚实的陆地，吃上新鲜的食物。许多人得了坏血病和其他疾病。所以，舰队立即进入蒙巴萨，强行实现了葡萄牙人的愿望。
他们遭遇了港口入口处要塞的强烈炮击。斯瓦希里人使用的枪炮是从各种失事的轻快帆船和大帆船中打捞上来的。要塞比遭遇阿尔梅达发动的攻击时坚固得多，这时候有4个葡萄牙叛徒操控这些大炮。这些炮手使得他们的同胞伤亡惨重，但是并不能阻止他们进入港口。他们要求苏丹投降，当苏丹表示拒绝时，达·库尼亚下令轰炸港口。轰炸持续了一整夜，3000名防御的士兵用万箭齐发回击他们的轰炸。当次日太阳升起时，一支火枪队带领数百人冲上了岸。无畏的葡萄牙军人再次证明他们锐不可当。
城里的人逃向大陆，胜利者占领了整座城市。这本是一场容易的征服，因为葡萄牙一方只有几个人伤亡。但是当达·库尼亚从宫殿的屋顶检阅胜利场景时，他的满足感注定是十分短暂的。他们与穆斯林游击队之间的小规模战斗十分频繁；雨水又不停，一直下到了年末，他的人因为得疟疾死亡率激增。葡萄牙人的身体已经非常虚弱，而船上的医生已将放血作为热疫的一种主要疗法。到舰队继续前往印度的旅程时，葡萄牙人死于战争和疾病的人数已经达到370人。
离开时，达·库尼亚想从马林迪指派一个顺从的谢赫就任蒙巴萨的新统治者。然而，这是一个接受起来有风险的荣誉，第一个被选出来的人拒绝了，他强调他的母亲曾经是一个奴隶，所以他无法升至这样的位置。另一位候选人要求达·库尼亚留下150名葡萄牙士兵保护他。鉴于葡萄牙人已经遭受的损失，达·库尼亚无法满足他的要求。
因此，达·库尼亚决定完全摧毁蒙巴萨。他下令推倒所有石制房屋，点燃所有能够焚烧的东西。根据一位葡萄牙编年史家的记载，“肆虐的火焰、冒烟的柱子，以及倒塌的石墙，使人想起地狱的惨象”。此外，这座城市的商业生活主要依赖的棕榈树被一排排砍倒。
达·库尼亚可以骄傲地向里斯本汇报说，蒙巴萨的要塞被摧毁了，这座城市已化为灰烬。但是，他们为这场胜利付出了高昂的代价，而且该城的居民仍然顽固抵抗。当蒙巴萨的苏丹返城查看烧毁的废墟时，他至少可以对他大难不死以图来日再战的臣民感到欣慰，并且他有充足的理由这样觉得。
在印度洋更广泛的冲突证明他们不是孤军奋战。不到10年，第一批土耳其船只到东非冒险。从那之后，葡萄牙人的焦虑与日俱增。他们加固沿海的几个小要塞，惩罚性地突袭支持土耳其的城镇，并且在1551年再次对蒙巴萨发起攻击。这次平民从他们背后发起了比上次更大规模的防御战，葡萄牙人不得不撤退到桑给巴尔，其统帅的脖子还中了一支毒箭。
但是，土耳其人一再证明他们在印度洋的海战中无法获得决定性的胜利。1554年之后，苏丹的决心有所动摇，因为著名的穆斯林地图绘制者皮里·雷斯精心计划的远征以失败告终，而他本人也被杀死。而在16世纪80年代，土耳其的挑战呈现出一种新的形式，它的领头者是阿米尔·阿里贝伊——一个大胆的海盗。他与葡萄牙人作过战，还在1581年突袭了他们在阿曼的要塞据点马斯喀特。他洗劫了那座城市，并且快速撤退。4年后，他率领两艘大帆船，再次从红海出发，但是其中一艘船太老旧了还渗水，以致于他们不得不在绕过非洲之角之前就把它丢弃。
阿里贝伊乘坐第二艘船到达摩加迪沙，在那里劝说民众与他们共命运，对奥斯曼帝国宣誓效忠。他被赠予更多的船只和数百名帮手，然后前往斯瓦希里海岸北端的拉穆和帕泰。这是一场虚张声势的胜利。当地统治者，以及远至南方的蒙巴萨的统治者都派来大使，告诉阿里贝伊他们多么想摆脱法兰克人。