В октябре 1486 года, вскоре после возвращения Кана — либо его кораблей, Жуан назначил одного из своих вельмож, Бартоломеу Диаша, командующим экспедицией, которая должна была отправиться на юг вдоль африканского побережья. Примерно в то же время и вторая — наземная — экспедиция тронулась в путь. Возглавлял ее Перу да Ковильян — сорокалетний путешественник, мореплаватель и шпион. Он не мог похвастаться происхождением, но обладал многочисленными талантами: в совершенстве знал арабский и кастильский языки, отлично дрался на мечах. Верный слуга короля, он долго прожил в Испании под прикрытием, выполняя секретные поручения, а также вел тайные переговоры в Марокко. Именно Ковильяну и еще одному отважному португальцу, говорящему по-арабски, Афонсу де Пайве, король доверил выполнение этой сложной операции.
Весной 1487 года, пока Диаш готовил корабли, Ковильян и Пайва проходили инструктаж у епископа Танжерийского и двух еврейских математиков, членов ученого совета, отказавшего Колумбу. Путешественники получили навигационную карту Ближнего Востока и Индийского океана с новейшими данными, доступными в Европе, — скорее всего, позаимствованными из работы Фра Мауро. 7 мая состоялась последняя тайная аудиенция в Сантарене под Лиссабоном, где король передал Ковильяну и Пайве верительные письма, которые надлежало вручить в Александрии. Среди присутствующих на аудиенции был восемнадцатилетний родственник короля дон Мануэл, герцог Бежу, для которого эта экспедиция будет впоследствии иметь особое значение.
Путешествие началось в Барселоне. Летом миссионеры добрались до христианского острова Родос, где пересели на другое судно, идущее в Александрию, ворота исламского мира. Но прежде раздобыли груз меда, дабы сойти за торговцев.
А в Лиссабоне Диаш был занят последними приготовлениями. Король дал ему две каравеллы и — поскольку плавание должно было занять длительное время — грузовой корабль для размещения дополнительного провианта, ибо «скудное питание или отсутствие оного на обратном пути ослабляет команду».
По примеру Кана эта экспедиция также везла каменные столбы, чтобы отмечать свое продвижение. Сам Диаш был очень опытный моряк, с ним ехали самые лучшие штурманы, и среди них Перу ди Аленкер, которому было суждено сыграть ключевую роль в Индийских кампаниях. Аленкера высоко ценил король Жуан, говоря, что «его опыт и мастерство достойны восхищения, уважения и щедрых наград». Штурманом грузового корабля был Жуан де Сантьягу, чье имя было высечено на скале при водопаде Йеллала и который помнил местонахождение последнего столба.
Небольшая флотилия отплыла из устья Тежу в конце июля 1487 года. Это была одна из самых значимых, но и самых загадочных экспедиций в истории мореплавания. Современные источники почти не упоминают о ней — лишь вскользь, в виде примечаний на картах и в книгах, — точно хроникеры отвернулись и смотрели в другую сторону. Понадобилось 60 лет, чтобы подробности, маршрут и результаты экспедиции были наконец описаны одним из историков шестнадцатого века, по имени Жуан де Баррош. Изначальный план был утерян, но, зная ход экспедиции, де Баррош восстановил его содержание. Сначала путь, как обычно, лежал на юг, по маршруту Диогу Кана, мимо воздвигнутых им столбов. Далее часть команды высадилась на берег и отправилась вглубь континента — по суше или по рекам — на поиски царства пресвитера Иоанна. Эта операция, совместно с Пайвой и Ковильяном, составляла твердую и последовательную стратегию для решения загадки Азии. Диаша сопровождали шесть африканцев — двое мужчин и четыре женщины, которые были во время оно похищены Каном и обучены португальскому. Их надлежало высадить на берег, в хорошей одежде, с золотом и серебром, и отправить к туземцам, дабы они разнесли по округе весть о богатстве и щедрости португальского короля, чьи суда находятся на побережье, поскольку он ищет пути в Индию и особенно правителя по имени пресвитер Иоанн. Женщин взяли потому, что они имели меньше шансов погибнуть в племенных стычках.
Тем временем Ковильян и Пайва, добравшись до Александрии, подхватили лихорадку и находились при смерти. А Диаш миновал последний столб, установленный его предшественником, и продолжал двигаться к югу. Каждый мыс и бухта на его пути получали название в честь святого, благодаря чему можно датировать продвижение экспедиции: залив Святой Марфы (8 декабря), Святого Фомы (21 декабря), Святой Виктории (23 декабря). К Рождеству они достигли бухты, названной залив Святого Христофора. Уже четыре месяца продолжалось плавание. Юго-западные ветры и встречное прибрежное течение заставляли часто менять курс. Несколько раз на берег высаживали несчастных посланников, один из которых успел по пути умереть. Остальные так и пропали без вести — по крайней мере, более о них нигде не упоминается. В какой-то момент было решено оставить грузовой корабль с командой из девяти человек на берегах Намибии и двигаться дальше налегке. В течение еще нескольких дней две каравеллы тащились мимо пустынных холмов, а затем штурманы приняли неожиданное решение. Находясь около 29° ю. д., они прекратили изматывающую борьбу с прибрежными ветрами и течениями и развернули корабли на запад, в открытый океан, с намерением позже взять курс на восток. Трудно сказать, как это произошло. Возможно, это был запланированный маневр или момент просветления, интуитивный ход, подсказанный опытом предыдущих экспедиций, которые сталкивались с похожей проблемой, находясь, правда, к северу от экватора. Иногда им приходилось отплывать на запад, в Центральную Атлантику, чтобы оттуда западные ветры отнесли их на восток, обратно в Португалию. Может быть, Диаш с товарищами надеялись, что подобное явление существует и в Южной Атлантике. Так или иначе, момент был исторический.