Am 9. März 1500 ging das Geschwader von Lissabon aus unter Segel. In der Nähe der Capverden wurde Luis Varez durch Sturm von den übrigen getrennt und kehrte nach Portugal zurück. Von der Guineaküste ab wurde gegen S.-W. gesteuert, um den Windstillen und widrigen Meeresströmungen auszuweichen. Vasco da Gama’s Segelvorschrift lautete, man solle in grade südlichem Cours bis zur Höhe des Caplandes segeln und dann mit günstigen Westwinden das gefürchtete Südende Afrikas zu umschiffen suchen. So kam es, daß die Schiffe durch den Aequatorialstrom weiter als beabsichtigt war, gegen Südwesten geführt wurden, wo sie am 21. oder 24. April etwa unter dem 18° s. Br. unvermuthet auf eine gebirgige Küste stießen, welche nach der Schätzung der Steuerleute etwa 450 Leguas von der afrikanischen Küste entfernt lag. Es war das Gestade Brasiliens, wohin eine günstige Meeresströmung sie durch Zufall getragen hatte. Daß bereits drei Monate früher Vicente Yañez Pinzon, einer der Begleiter des Columbus auf seiner ersten Fahrt, etwa 10 Grad weiter nördlich dieselbe Küste berührt hatte, war auf der portugiesischen Flotte noch nicht bekannt. Es wird aber aus den durch die Meeresverhältnisse geleiteten Fahrlinien der Portugiesen klar, daß die neue Welt von ihrem südlichen Halbcontinente aus über kurz oder lang von den Indienfahrern gefunden werden mußte, auch wenn der kühne Plan eines Columbus keine Unterstützung gefunden hätte und nicht zur Ausführung gelangt wäre. Der Gang der Ereignisse brachte diese Entdeckung von selbst mit sich.
Cabral segelte mehrere Tage an dem Ufer des waldigen Landes hin, besuchte die Bucht des Porto-Seguro und verkehrte wiederholt mit den braunen Eingebornen, die fast unbekleidet, ohne Metallwaffen, unter leichten Strohdächern in Netzen aus Baumwollschnüren schliefen. Am 3. Mai, dem Tage der Kreuzes-Erfindung nahm Cabral von dem Lande Abschied, dem er den Namen Terra de Sa. Cruz beilegte, eine Benennung, die sich aber bald änderte, nachdem man den Reichthum an Farbeholz (Rothholz) entdeckt hatte. Dieses Holz nannten die Portugiesen Brazil (nach der Farbe glühender Kohlen) und daher bekam jene Küste bald den Namen Terra de Brazil, Brasilland, Brasilien.[94] Der Capitän Gaspar de Lemos erhielt den Auftrag, mit der Meldung der neuen Entdeckung nach Portugal zurückzukehren und unterwegs so viel als möglich von der weiter nördlich verlaufenden Küste aufzunehmen.[95] Cabral segelte quer über den südatlantischen Ocean nach dem Caplande zu. In einem schweren Unwetter, welches zwanzig Tage dauerte, wurden am 23. Mai in der Nähe des Cap der guten Hoffnung vier Schiffe gekentert und gingen zu Grunde, darunter auch das Schiff des Bartolomeu Dias. Als ein eigenthümliches Verhängniß, daß der Entdecker des Cap hier sein Grab in den stürmischen Wogen finden sollte, sieht es auch Camoēns an, der den Genius des Sturmcaps also reden läßt:
Vernimm, daß so viel Schiff’ auf dieser Reise
Dir kühnlich folgen hin zu deinem Ziel, —
Die soll als Feinde hier in meinem Kreise
Bedrohen jeder Sturm, der sie befiel;
Die Flotte, welche unerlaubter Weise
Zuerst hieher zu lenken wagt den Kiel,
Die will ich gleich mit solcher Straf beladen,
Daß größer als die Fährniß sei der Schaden.