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