Этот путь для командора флотилии был своеобразной проверкой способности к выполнению возложенной на него задачи. Ему пришлось иметь дело с неизвестными ветрами и течениями, неожиданными и свирепыми штормами. Гама благодаря находчивости, таланту руководителя и организатора сумел блестяще справиться с ситуацией и завоевать доверие и восхищение как офицеров, так и матросов. С последними он был справедлив и прост в обращении. Особенный восторг команды вызвал его поступок во время одной из высадок на берег. На празднике, который устроили в честь гостей туземцы, матросы начали танцевать. По примеру португальских королей с ними танцевал и Гама.

22 ноября флотилия обогнула мыс Доброй Надежды. Дальше предстояло плыть в неизведанных водах. 25 декабря мореплаватели вошли в бухту, названную ими в честь праздника Гаванью Рождества (совр. порт Наталь). Они двинулись дальше, преодолевая сильное течение. Только 23 января 1498 г. им удалось достичь устья реки Замбези, где экспедиция пробыла целый месяц, готовясь к плаванию по Индийскому океану. Нужно было починить корабли. Но самое главное, моряки начали болеть цингой – бичом всех мореплавателей тех и более поздних времен. О том, насколько сложным было положение, можно судить по письму члена команды Филиппа Сасетти, который сообщил, что в один день заболели сразу 160 человек, что их десны и ноги распухали до чудовищных размеров. Матросы вынуждены были бритвами обрезать десны, «чтобы можно было открыть рот». Через несколько дней многие умерли, «угасая, словно лампада, в которой выгорело масло». Когда у туземцев были выменяны свежие продукты, страшная болезнь вскоре сама собой прекратилась.

Наконец флотилия, полностью готовая к плаванию, двинулась на северо-восток и 2 марта достигла острова Мозамбик. Здесь заканчивались земли «диких» племен и начинался богатый мир, контролируемый арабо-мусульманами. До прибытия португальцев в их руках была сосредоточена вся торговля в Индийском океане. Для общения с арабами нужны были недюжинные дипломатические способности, которыми Гама, увы, не обладал. Именно с этого времени начали проявляться его горячность, недостаток такта и рассудительности, бессмысленная жестокость.

Вначале шейх и жители Мозамбика отнеслись к португальцам терпимо. Они приняли их за мусульман, однако были недовольны подарками, которые прибывшему на корабль шейху попытался вручить Васко. Это был никому не нужный хлам, а восточные правители привыкли к иному отношению. Вскоре стало известно, что люди с непривычных взорам арабов кораблей являются христианами. Напряжение росло, и 11 марта португальцы подверглись нападению. Атаку удалось отбить, но для решительного сражения у команды, значительно сократившейся после эпидемии цинги, не было сил. Пришлось спешно покинуть негостеприимный берег.

7 апреля путешественники прибыли в Момбасу, но вскоре, не заходя в гавань, вынуждены были покинуть и ее, узнав о намерении момбасского короля захватить корабли и взять команду в плен (сведения были получены от заложников, которых пытали кипящим маслом). В восьми милях от гавани взбешенные португальцы захватили барку, груженную золотом, серебром и съестными припасами.

14 апреля флот подошел к Мелинде, богатому мусульманскому городу. Местный шейх враждовал с правителем Мозамбика и был рад заключить союз с Гамой. В ответ на знаки внимания со стороны правителя португалец отослал ему воистину «царский дар»: монашескую рясу, две нитки кораллов, три шляпы, тазики для омовения рук, бубенчики и два куска дешевой полосатой материи. В другой ситуации шейх, возможно, не стерпел бы такого неуважения, но сейчас он боялся непрошеных гостей и согласился дать искусного лоцмана, необходимого для дальнейшего плавания. Им стал Ахмед ибн Маджида, носивший арабско-санскритское прозвище Малемо Кана – «ведущий по звездам». С его помощью в середине мая 1498 г. экспедиция добралась до Малабарского берега. Корабли бросили якоря близ крупнейшего индийского города Каликут (Кожикоде). Долгожданный морской путь в Индию был разведан.