Зная по опыту, что бухта мелководна, и опасаясь, что какой-нибудь из кораблей, как ранее «Беррио», снова застрянет, да Гама попросил у султана дать им лоцмана. Тот дал двоих и велел заплатить золотом. Взаимное недоверие нарастало. В субботу 10 марта, когда корабли отплыли и взяли курс к острову, находящемуся в 3 милях, чтобы тайно отслужить там мессу, один из лоцманов прыгнул за борт. Навстречу шлюпкам, которые были спущены в погоню, с острова вышли шесть вооруженных кораблей, дабы вынудить португальцев вернуться в порт. К этому времени, скорее всего, местные догадались, что они не мусульмане. Залпы из орудий обратили нападавших в бегство.

Время поджимало, надо было срочно уезжать. Однако вмешалась погода. Встречным ветром корабли отогнало обратно к острову, где они задержались на десять дней. Султан пробовал помириться, высылая переговорщиков, но португальцы не верили ему. К несчастью, на острове не было ни ручья, ни другого источника, а вода у моряков заканчивалась. В ночь 22 марта они предприняли попытку вернуться в порт Мозамбик, прихватив с собой второго лоцмана, которого все это время держали у себя. Но лоцман либо не хотел, либо не мог найти источник. Вечером следующего дня был обнаружен ручей, который охраняли двадцать человек. Артиллерийскими залпами португальцы разогнали охрану, но набрать воды не смогли. Борьба за воду продолжалась до 25 марта, пока постоянный пушечный огонь не вынудил охрану скрыться в городских стенах. Набрав воды, португальцы схватили на берегу несколько заложников — в целях более успешной навигации, дали на прощание пару залпов по городу и отбыли.

Настроение у всех было подавленное. Моряки не без оснований опасались, что так пойдет и дальше. Капитаны лютовали, срывая зло на команде. Требовалось срочно пополнить запасы провизии и найти надежный дружественный христианский порт, однако такого шанса все не выпадало. Продвижение к северу происходило с трудом. Дул встречный ветер, пленный лоцман — по оплошности либо по злому умыслу — не указал порт Килва, где, как предполагали португальцы, живет много христиан. Негодник был выпорот, а экспедиция вскоре прибыла в порт Момбаса.

«В Вербное воскресенье мы с радостью бросили якорь в Момбасе, — пишет хроникер, — ибо надеялись назавтра сойти на берег и присутствовать при мессе совместно с христианами, которые, по сообщениям, проживали в городе, в отдельном от арабов квартале». Расстаться с мечтой о христианском сообществе было нелегко.

Но высадка в Момбасе не состоялась. Вначале португальцев приветствовал султан. Двое из команды — скорее всего, заключенные — отправились на берег, где их хорошо приняли. Они встретили «христиан», «которые показали им бумагу, объект своего поклонения, с изображением Духа Святого». Таково было одно из самых глубоких, почти комических ранних заблуждений португальцев насчет индуистов, о которых они ничего не знали и долго принимали за христианскую секту с их собственными иконами. Эти люди, поклоняющиеся неизвестным европейцам антропоморфным образам, соответствовали представлению о далеких христианских общинах, бытовавшему в Европе.

Султан хотя и прислал образцы пряностей, предлагая сделку, но слухи о мозамбикском инциденте явно опередили их. Когда португальцы, поверив султану, направились в порт, дрейфующий «Габриэл» наткнулся на другое судно. Лоцманы, очевидно из страха перед наказанием, прыгнули за борт, где их подобрали местные лодки. Португальцы занервничали. Ночью они под пыткой вырвали у двоих заложников «признание», что султан велел задержать суда в отместку за обстрел Мозамбика. На следующий день португальцы собирались продолжить, но оба заложника бросились в море — хотя руки у них были связаны, — предпочтя смерть пытке кипящим маслом.

В полночь вахтенные заметили в залитом лунном свете море нечто, поначалу принятое ими за косяк тунца. Оказалось, что это люди, которые бесшумно приближались к кораблям. Добравшись до «Беррио», они сначала попробовали перерезать якорный трос, потом полезли на ванты, но, «поняв, что их обнаружили, прыгнули в море и убрались».

Утром 13 апреля флотилия взяла курс на Малинди, в 70 милях к северу, в надежде встретить там более дружественный прием. Хроникер отмечает, что больные цингой начали выздоравливать, «потому что климат в этих местах уж очень хорош». Скорее всего, улучшение наступило благодаря местным апельсинам, содержащим витамин С, большой запас которых сделали португальцы.

И все-таки силы путешественников были на исходе. После очередной остановки один из якорей пришлось обрубить, потому что матросы не смогли втащить его на борт. Однажды португальцы увидели в море две лодки и бросились в погоню, ибо нуждались в лоцмане для навигации в прибрежных водах. Первый из захваченных сбежал, они поймали второго. Все семнадцать пассажиров лодки, включая старика благородной наружности и его жену, бросились за борт, чтобы не попасть в руки пиратов, однако португальцы захватили всех, а также забрали груз, бывший на лодке: золото, серебро, большое количество маиса и другой провизии. С тех пор грабить суда и брать заложников стало для них обычным делом.

К вечеру 14 апреля экспедиция достигла Малинди. Хроникер ностальгически описывает высокие беленые дома во много окон среди плодородных полей и зелени, которые, вероятно, напоминали ему родной городок на берегах Тежу. Назавтра была Пасха, но никто не объявлялся с визитом. Слухи и здесь опередили их приезд. Да Гама высадил на отмели против города старика-пленника, поручив тому посредническую миссию. Первоначальный ответ султана был по традиции благожелателен. Старик вернулся и передал, что «султан будет рад познакомиться и предоставить капитану все, что есть в его землях, а также лоцманов». Да Гама подогнал корабли ближе к берегу, но от высадки отказался, говоря, что «его господин» запретил им покидать суда. Переговоры состоялись в море на лодках и прошли довольно успешно. Султан прислал овец и пряности, попросил записать ему имя монарха и изъявил желание отправить к нему послов или письмо. Смягчившись, да Гама в знак доброй воли отпустил заложников. Так португальцы неожиданно для себя получили первый урок политической дипломатии, принятой среди народов Индийского океана. Дело в том, что султану требовались союзники для борьбы с торговыми конкурентами. Христианам еще предстояло научиться оборачивать подобные союзы себе на пользу, разжигая религиозную вражду и утрируя религиозные различия соперников. Ну а пока стороны с безопасного расстояния обменивались церемониальными любезностями. «Султан с удовольствием объехал наши корабли, а бомбарды дали залп в его честь», — пишет хроникер. Последовал обмен визитами: снова на берег выслали заключенных. Султан на бронзовом троне восседал у воды в окружении музыкантов, играющих серенады. Рядом разыгрывали представление конные всадники. Но да Гама все-таки отказался сойти на берег и посетить престарелого отца султана.

Между тем португальцы с радостью узнали о прибытии в Малинди четырех судов индийских христиан, и вскоре эти «христиане» поднялись к ним на борт. Увидев изображение распятого Христа и Богоматери, индийцы упали ниц и принялись молиться. С собой они привезли гвоздику, перец и другие ценности. На кораблях у них были пушки, порох, и ночью, под крики «Христос! Христос!» небо расцветилось красочным салютом в честь единоверцев. На ломаном арабском они просили да Гаму не сходить на берег и не доверять мусульманам. Подобных христиан португальцы видели впервые. «Эти индийцы очень смуглые, — замечает автор дневника, — одежды на них мало. Они носят длинные бороды, волосы заплетают в косы. Они сказали нам, что не едят говядины».