König Johann II. hat aber bei der Suche nach Indien nicht nur auf ein Pferd gesetzt. Kurze Zeit nachdem de Covilhao und de Paiva auf Geheiß ihres Herrschers Lissabon verlassen haben, bricht noch eine zweite Expedition auf – dieses Mal auf dem Seeweg. Zunächst einmal mussdabei jedoch eine schier unüberwindliche Hürde genommen werden: Die erste Umseglung Afrikas im Süden.
Bartolomeu Diaz, Leiter der Expedition von königlichen Gnaden, weiß noch nichts von den Informationen, die de Covilhao in Sofala an der Ostküste Afrikas in Erfahrung bringt, als er im Spätsommer 1487 mit zwei Karavellen und einem Proviantschiff zu seiner Reise ins Ungewisse aufbricht. Bis zum Kongo und dann bis zum Kap Cross ist der Weg bekannt. Diaz lässt während der Fahrt zu jeder günstigen Gelegenheit Proviant aufnehmen oder mit den Eingeborenen Tauschgeschäfte beginnen, um die Versorgung der Mannschaft zu sichern und die Matrosen bei Laune zu halten.
Am Kreuzkap, wie das Kap Cross auch genannt wird, hören die Land- und Seekarten auf, hier beginnt das Abenteuer richtig. Immer weiter nach Süden dringen die Seefahrer vor. Dabei entdeckten sie unter anderem die Bucht Angra dos Voltas an der Küste des heutigen Namibias. An jedem passenden oder unpassenden Punkt seiner Route lässt Diaz steinerne Wappensäulen – sogenannte Pradaos – an den neuentdeckten Küsten aufstellen, um den Machtanspruch Portugals auf diese Gebiete zu dokumentieren.
Ende Januar 1488 aber gerät die kleine Flotte in schwere See. Ein gewaltiger Sturm sorgt dafür, dass Diaz und seine Gefährten fast vollständig die Orientierung verlieren. Meterhohe Wellen, kein Land in Sicht – was tun? Diaz legt einen Ostkurs fest, in dem festen Glauben, dort auf Land zu treffen. Aber weit gefehlt. Auch nach tagelanger Suche zeigt sich kein Hinweis auf die afrikanische Küste am Horizont. Diaz und seine Begleiter sind ratlos.