Обогнув южноафриканский берег, корабли вошли в Мозамбикский пролив (между Африкой и Мадагаскаром) и 2 марта пристали к порту Мозамбик (у северного конца пролива). Португальцы увидели утопавший в зелени город и порт со множеством больших и малых судов. Васко да Гама узнал через переводчика, владевшего арабским языком, что на этих берегах можно встретить много поселений и городов, основанных арабскими работорговцами и купцами, ведущими торговлю с Индией. Золото, серебро, ткани и пряности, жемчуг и рубины составляли главный предмет торга. Таким образом, португальская флотилия попала в области, находившиеся под мавританским влиянием. Арабы контролировали все торговые пути и доставляли восточные товары в Александрию, Каир, Оран и другие города, а оттуда генуэзские и венецианские суда переправляли эти товары в страны Европы. Арабы были хозяевами Индийского океана, и португальцы, прежде чем завоевать Индию, должны были сломить могущество арабов.
Местный шейх, полагая, что он имеет дело с мусульманами, нанес визит португальцам, которые встретили его весьма учтиво и подарили ему несколько нитей коралла и красный колпак. Важный холеный шейх из вежливости принял этот скромный подарок, но при повторном визите, когда португальцы стали его снова одаривать такими же пустяками, с презрением отвернулся от этих убогих даров. Вскоре шейх узнал, что чужеземцы – христиане, злейшие враги магометан, и, пристыженный тем, что поддался на обман, решил устроить избиение «неверных». Однако он действовал недостаточно осторожно: матросы, отпущенные на берег, сразу же почувствовали ненависть местных жителей. Когда дело начало доходить до открытых столкновений, Васко да Гама отвел флотилию к небольшому острову (Сан-Жоржи) и, прежде чем окончательно покинуть Мозамбик, приказал своим людям захватить во что бы то ни стало одного или двух лоцманов, так как нанятые с помощью шейха лоцманы-арабы сбежали с полученным вперед жалованием. Португальцы захватили в окрестной деревушке двух лоцманов, но затем подверглись нападению, когда высадились на берег за водой. В ответ на этот враждебный выпад Васко да Гама стал обстреливать город из бомбард, вынудив шейха запросить мира. Тем не менее через несколько дней начались новые стычки, и португальцам лишь с большим трудом удалось запастись питьевой водой. На прощанье Паулу да Гама захватил два туземных баркаса, разделив богатый груз между своими офицерами и матросами, а Васко да Гама приказал еще раз обстрелять из бомбард этот негостеприимный берег.
Только 29 марта подул благоприятный ветер, и корабли снова пустились в путь. Но арабский лоцман притворился, будто не понимает, чего хотят от него чужеземцы. Тогда Васко да Гама, чтобы положить конец упрямству этого мавра, приказал «как следует» его высечь. Остров, мимо которого португальцы проплывали во время экзекуции, получил название Илья-ду-Асоутаду (Остров высеченного.)
7 апреля флотилия подошла к Момбасе, портовому городу, в котором, по уверению высеченного лоцмана, была колония христианских купцов.
Корабли стали на якорь в открытом море, не рискуя войти в гавань, несмотря на восторженный прием, который был оказан здесь португальцам. Их настойчиво зазывали в город, но Васко да Гама, подозревая предательство, не решился нанести визит местному шейху. Ночью к флагманскому кораблю приблизилась завра (мавританский баркас) с сотней вооруженных людей. Они попытались было перелезть через борт, но Гама разрешил подняться только нескольким. Удалились арабы столь же неожиданно, как и прибыли.
Шейх Момбасы, по-видимому уже извещенный о том, что произошло в Мозамбике, боялся открыто напасть на португальцев. Прикидываясь другом, он присылал щедрые подарки, в том числе апельсины, благодаря которым многие матросы избавились от цинги, обещал нагрузить корабли пряностями, как только они войдут в порт, уговаривал португальцев открыть у него в городе торговую факторию, а по ночам продолжал посылать к месту стоянки завры с воинами, упорно пытавшимися обрубить якорные канаты и потихоньку забраться на португальские корабли.
Чтобы узнать истинные намерения шейха, Васко да Гама приказал подвергнуть пытке двух захваченных арабов. С хладнокровной жестокостью капитан-командир допрашивал несчастных пленников, капая им на спину кипящую смесь смолы и масла. Арабы сознались, что шейх решил заманить корабли в гавань и отомстить португальцам за то, что они натворили в Мозамбике. Не довольствуясь этими показаниями, Гама велел продолжать пытку, но пленники внезапно рванулись вперед и бросились за борт со связанными руками.
В ожидании попутного ветра португальцам пришлось еще два дня стоять у Момбасы. Лишь 13 апреля флотилия двинулась дальше, захватив в нескольких лигах от места стоянки небольшое арабское судно с богатым грузом золота и серебра. На другой день корабли стали на якорь у Малинди, одного из самых богатых арабских городов. С моря он казался особенно красивым. Сверкавшие в солнечных лучах позолоченные минареты и ослепительной белизны мечети отчетливо выделялись на фоне синего неба.