В целях осуществления своего плана король направляет двух своих рыцарей Кавильау и Пайва, которые свободно владели арабским языком, в путешествие в Египет и другие страны Ближнего Востока, куда доступ европейцам был практически закрыт. Их главная задача заключалась в сборе наиболее полных сведений относительно торговых путей в Индию и о месте нахождения предполагаемого христианского королевства во главе с пресвитером Иоанном, которое, согласно более поздним легендам, существовало где-то в неведомых землях африканского континента. Выйдя из Лиссабона в мае 1487 года, этот дуэт королевских разведчиков под видом купцов отправился на остров Родос, приобретя по пути большое количество меда якобы для ведения торговли. Оттуда они переправились в Александрию, а затем в Аден, где их пути разошлись. Пайва направился в Эфиопию искать христианское царство пресвитера Иоанна, но, серьезно заболев в дороге, был вынужден вернуться в Каир, где его настигла смерть. Путь Кавильау из Адена шел морским маршрутом в Калькутту, откуда он направился в Гоа. Здесь он вносит в свои записи сведения об активной торговле специями, драгоценными камнями, арабскими лошадьми и хлопком. Далее его путешествие следует в стратегически важный порт Ормуз. Оттуда этот смелый агент погружается на арабское судно и отправляется в плавание вдоль восточного побережья Африки на юг к Зимбабве, где с древнейших времен добывали и экспортировали золото. От арабских капитанов и лоцманов Кавильау собирает ценные сведения, которые убедительно свидетельствуют о том, что Индийский океан действительно соединяется с водами Атлантики у самых южных берегов Африки.
Собрав достаточно нужной информации, которую он спешил передать королю, Кавальау направляется в Каир, где его уже дожидались два других королевских агента, оба прекрасно говоривших по-арабски. Будучи евреями, они могли свободно передвигаться по странам Ближнего Востока Жоау Второй послал их на помощь Кавальау, когда ему сообщили о скоропостижной смерти Пайвы. Получив от Кавальау секретные сведения, один из них — сапожник по имени Жоау ди Ламегу — сразу же отплыл с донесением в Лиссабон, а второй — раввин Авраам — присоединился к неутомимому Кавальау, который снова поехал в Ормуз для сбора данных об оборонительных сооружениях этого важнейшего стратегического порта на выходе из Персидского залива в Индийский океан. Когда эта часть секретной миссии была успешно завершена, неукротимый Кавальау передает собранные им сведения раввину Аврааму и отправляет его с одним из арабских караванов в Сирию, откуда тот уже морским путем прибывает с ценным донесением в Лиссабон.
Но теперь, после смерти Пайвы, король передает невыполненную последним миссию по обнаружению царства пресвитера Иоанна его более удачливому коллеге. Продолжая свои фантастические для той эпохи секретные детективные приключения, Кавальау перебирается из Ормуза в Мекку — самое священное для мусульман место, которое было закрыто для посещения «неверными». Отсюда через Синайский полуостров, где он посещает монастырь Святой Екатерины, его путь продолжился к сомалийской стороне залива Адена, лежащей на подступах к высокому плато Эфиопии. Добравшись до него, Кавальау затем попадает в столицу этой страны, где его радушно принимает ее христианский правитель копт Негус Португальскому тайному агенту удалось установить, что в глубинах африканского континента действительно существует христианское царство, но оно не было царством пресвитера Иоанна, а страной черных эфиопов. Выполнив вторую и последнюю часть своей тайной королевской миссии, Кавальау приготовился к возвращению в Португалию с донесением Жоау Второму. Однако умный и ловкий португалец настолько понравился царю Эфиопии, что тот, предоставив ему всяческие блага, запретил его выезд из своей страны. По всей вероятности, и сам Кавальау, оказавшись в столь привилегированном положении при дворе высшего местного правителя, не очень стремился вернуться к гораздо более скромным условиям жизни на своей родине. Оставшись после трех лет необыкновенных приключений по выполнению тайных поручений короля в открытой им для Португалии стране, он удивительно в ней преуспел, женился на женщине из знаменитого местного рода и вырастил семью. 30 лет спустя после прибытия в Эфиопию, то есть в 1520 году, Кавальау радостно приветствовал в этой далекой земле первое европейское посольство. Это было посольство из Лиссабона.
Вооружившись ценными сведениями от своих тайных агентов, Жоау Второй теперь был уверен в том, что в Индию можно было пройти из Европы морским путем вокруг Африки, и, не теряя времени, он вновь снаряжает экспедицию для нахождения такого маршрута. На этот раз во главе двух каравелл и большого корабля с провиантом и разными запасами он назначает придворного рыцаря и опытного капитана Бартоломеу Диаша, которому уже доводилось командовать кораблем в экспедиции на Золотой Берег. Король дает Диашу совершенно четкое и строгое указание пройти за самую южную точку оконечности Африки, до которой удалось дойти Диогу Кау почти три года тому назад, то есть мыс Круис, а затем проплыть дальше в поисках пути в Индию. Дойдя до залива Тигров несколько севернее мыса Круис, Диаш оставляет на хорошей якорной стоянке грузовой корабль, а сам во главе двух каравелл следует дальше на юг.