Среди экипажа было несколько моряков, принимавших участие в экспедиции Бартоломеу Диаша, в том числе лучший португальский лоцман Перу ди Аленкер. Весь экипаж армады, включая и десятерых преступников, взятых для исполнения самых опасных поручений, состоял приблизительно из ста шестидесяти — ста семидесяти человек.
Наступило 8 июля. При первых лучах солнца Васко да Гама в сопровождении своих офицеров среди громадного стечения народа приблизился к кораблям. Вокруг него образовалась свита из монахов и священников, которые читали молитвы и отпускали грехи уходящим в далекое опасное плавание. По ветру реяли флаги, солдаты трубили в трубы, вопли и причитания людей, провожавших своих близких, смешивались с восторженными криками зрителей. Поднятые паруса с алыми крестами, раздуваемые попутным ветром, рвались в открытое море, увлекая в сказочно богатую Индию надежды Васко да Гама и его спутников…
На первом этапе экспедиции, до крепости Сан-Жоржи-да-Мина на Гвинейском берегу, откуда португальцы вывозили золото и рабов, флотилию сопровождал корабль, которым командовал Бартоломеу Диаш, назначенный правителем этой крепости.
Плавание началось спокойно, при попутном ветре. Уже через неделю корабли оказались в виду Канарских островов. В ночь на 17 июля возле бухты Рио-де-Оро (Золотая река) спустился густой туман, и корабли разлучились друг с другом. Предвидя такую возможность, Гама заблаговременно приказал держать курс на острова Зеленого Мыса. Здесь, у острова Сантьягу, корабли снова собрались вместе. Возобновив запасы мяса, воды и дров, 3 августа флотилия двинулась дальше на юго-восток, и утром 4 ноября тоскливым взорам мореплавателей открылся берег Африки. Однако прошло еще три дня, прежде чем удалось найти удобную бухту.
Там португальцы впервые увидели бушменов, которых приняли за низкорослых негров. Матросы захватили и доставили на корабль одного насмерть перепуганного туземца. Переводчики так и не поняли его «бормотанья», и Гаме, после того как туземец был хорошо накормлен и немного успокоился, пришлось объясняться с ним жестами. Перед дикарем разложили образцы пряностей, жемчуг, золото, серебро, но он, впервые увидев эти драгоценные предметы, не проявил к ним никакого интереса.
Позже выяснилось, что эти «низкорослые негры», прикрывавшие наготу древесной корой, очень ловко владели своим примитивным оружием — деревянными дротиками с наконечниками, закаленными на огне. Когда один матрос, некий Фернан Вилозу, случайно чем-то обидел дикарей, те погнались за ним и завязали настоящее сражение с его защитниками, среди которых оказался и сам Васко да Гама; во время этой битвы он был ранен стрелой в ногу. Из-за опрометчивости Вилозу португальцы были вынуждены поскорее сняться с якоря. Описанный случай послужил затем Луишу ди Камоэнсу материалом для одного из лучших мест в его знаменитой поэме «Лузиады».
Покинув остров Святой Елены, бывший лоцман Диаша Перу ди Аленкер заявил, что, как он полагает, до мыса осталось не более тридцати морских лиг; но командир экспедиции усомнился в этом, взял курс в открытое море, и 18 ноября флот оказался в виду мыса Доброй Надежды.
Двадцать второго ноября флотилия благополучно обогнула мыс Доброй Надежды и через три дня остановилась в бухте, которую путешественники назвали Сан-Браш (теперь Моссел).
Это была та самая Гавань пастухов, где у Бартоломеу Диаша десять лет тому назад произошло столкновение с туземцами. Надо было держаться настороже. Но местные бушмены оказались доверчивыми и незлобивыми. Они с восторгом принимали подарки — погремушки и бубенчики, пригоняя взамен коров и овец. Желая закрепить дружбу с белыми людьми, бушмены стали в круг и начали плясать под аккомпанемент флейт. Музыка и танцы дикарей произвели на португальцев большое впечатление.
«Тогда они начали играть на четырех или пяти флейтах, — пишет в своем дневнике один из спутников Васко да Гамы, имя которого осталось неизвестным. — Некоторые издавали высокие звуки, другие — низкие, создавая таким образом гармонию, изумительную для негров, от которых нельзя было ожидать ничего подобного. И они продолжали танцевать на свой лад, а капитан-командир приказал трубачам играть, и мы танцевали на наших кораблях. Капитан-командир сам присоединился к нашим танцам и очень нас развеселил».