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