In Paris lernte Humboldt den schwedischen Konsul des türkischen Algier kennen, der sich auf der Durchreise nach Marseille befand, von wo ihn eine schwedische Fregatte nach Nordafrika bringen sollte. Der Konsul glaubte, beim Bey von Algier für Humboldt die Erlaubnis erwirken zu können, das noch von keinem Mineralogen untersuchte Atlasgebirge bereisen zu dürfen. Auch schickte der Bey jedes Jahr ein Schiff nach Tunis, mit dem Mekka-Pilger nach Ägypten fuhren; Humboldt sollte es ebenfalls benutzen können. Kurzentschlossen hasteten Bonpland und er nach Marseille, um die schwedische Fregatte nicht zu verpassen, aber die Fregatte kam und kam nicht nach Marseille. Nach zwei Monaten ungeduldigen Wartens erfuhren sie aus den Zeitungen, dass das Schiff vor der Küste Portugals in einen Sturm geraten und schwer beschädigt worden war und das spanische Cádiz hatte anlaufen müssen, um repariert zu werden, was mindestens ein halbes Jahr in Anspruch nehmen würde. Zertrümmerte Masten, zertrümmerte Hoffnungen. Doch Humboldt gab nicht auf. Im Hafen von Marseille lag ein kleines Schiff aus Ragusa (Dubrovnik), das im Begriff stand, nach Tunis auszulaufen: eine günstige Gelegenheit, näher an Ägypten und Syrien heranzukommen. Sie einigten sich mit dem Kapitän über den Preis für die Überfahrt, am nächsten Tag sollten sie unter Segel gehen, im letzten Moment verzögerte sich die Abfahrt wegen einer Kleinigkeit – glücklicherweise, denn so erreichte sie noch die Nachricht, dass die Regierung in Tunis neuerdings alle dort ansässigen Franzosen verfolge und alle aus französischen Häfen kommenden Personen ins Gefängnis werfe. Aus der Traum. Humboldt und Bonpland beschlossen, den Winter in Spanien zu verbringen, in der Hoffnung, sich im folgenden Frühjahr in Cádiz oder Cartagena nach dem Orient einschiffen zu können. Ende Dezember 1798 machten sie sich auf den Weg nach Katalonien.
In Madrid wies der sächsische Gesandte am spanischen Hof Humboldt darauf hin, dass die Möglichkeit bestehe, von der Regierung die Erlaubnis zu erhalten, auf eigene Kosten durch das Innere Spanisch-Amerikas zu reisen. Humboldt erhielt Zugang zur Regierung und in der Frühjahrsresidenz Aranjuez eine Audienz beim König, bei der er Gründe und Vorteile einer Forschungsreise in die spanischen Besitzungen von Amerika und nach den Philippinen darlegte, die er später in einer Denkschrift ausformulierte. Der Vorschlag wurde wohlwollend aufgenommen und Humboldt ermächtigt, mit seinem »Diener« (Bonpland) nach Spanisch-Indien überzusetzen und dort alle Beobachtungen, Messungen, Probeentnahmen und sonstige Studien durchzuführen, die er zur Förderung der Wissenschaften für angebracht hielt. Er begab sich mit Bonpland nach La Coruña, wo sich ihre Einschiffung nach Kuba verzögerte, weil drei britische Schiffe den Hafen blockierten; England hatte eine Seeblockade über das napoleonische Frankreich und verbündete Länder verhängt. Am 5. Juni 1799 stahl sich die Korvette »Pizarro« bei dichtem Nebel und günstigem Wind aus dem Hafen, obwohl die Küstenwacht ein britisches Geschwader vor der Nordwestecke Spaniens signalisiert hatte. Vor der Küste Portugals sichtete die »Pizarro« einen weiteren englischen Konvoi und wich im Schutz der Dunkelheit von ihrem Kurs ab, um nicht von den Brits gejagt zu werden. Bei ihrer Ankunft in Santa Cruz de Tenerife lief sie im dichten Nebel an mehreren britischen Schiffen vorbei, ohne sie zu bemerken und von ihnen bemerkt zu werden. Wäre sie aufgebracht worden, hätten Humboldt und Bonpland sich von ihrem amerikanischen Traum verabschieden können und wie alle anderen Passagiere ihrer Rückführung nach Europa entgegengesehen.
Humboldt war begeistert von Teneriffa, insbesondere von der Vegetation und der Gartenlandschaft im Westteil der Insel und vom Teide, gegen den der Vesuv bloβ ein Hügel war. Der Kapitän der »Pizarro« hatte Befehl zu warten, bis Humboldt von der Besteigung des Teide zurückkehrte. »Fast mit Tränen reise ich ab«, schrieb Alexander seinem Bruder Wilhelm in einem Brief aus Orotava, »ich möchte mich hier ansiedeln«. Vorerst aber lockten die Tropen. Auf der Überfahrt nach Amerika wurde er nicht müde, nachts die Schönheit des südlichen Himmels zu bewundern, und es erfüllte sich ein Jugendtraum, als er zum ersten Mal das Kreuz des Südens erblickte. Doch die Tropen zeigten sich auch von ihrer hässlichen Seite. Auf der »Pizarro« brach ein bösartiges Fieber aus, mehrere Infizierte delirierten schon am zweiten Tag nach den ersten Anzeichen, die Krankheit drohte epidemisch zu werden, nicht eine Unze Chinarinde befand sich an Bord, nur ein Ignorant von Wundarzt, der Aderlässe verordnete. Gleich vielen anderen Passagieren beschlossen Humboldt und Bonpland, in Cumaná (Venezuela), dem östlichsten Hafen Spanisch-Amerikas, an Land zu gehen und später mit einem anderen Paketboot nach Kuba oder Mexiko weiterzusegeln. Sie wollten den Zwischenstopp von ein paar Wochen dazu nutzen, das Hinterland Cumanás ein wenig zu erkunden; aus einigen Wochen wurde dann mehr als ein Jahr. Ohne die Seuche an Bord der »Pizarro« wären sie nie an den Orinoko und bis an die Grenze der portugiesischen Besitzungen am Río Negro gekommen.
Wunder über Wunder fanden Humboldt und Bonpland in Cumaná und Umgebung: Bäume mit ungeheuren Blättern und Blüten, Vögel und Fische in leuchtenden Farben, prachtvolle Pflanzen, von denen sie 1600 sammelten, darunter 600 unbekannte – eine verschwenderische Überfülle der Natur. »Ich fühle es, dass ich hier sehr glücklich sein werde«, gestand Humboldt seinem Bruder. Über Caracas zogen sie auf Maultieren in die Llanos, diese weite, unermessliche, völlig ebene Einöde ohne jegliche Anhöhe, ebener als die Wüste oder selbst das Meer, aber heiβ und stauberfüllt wie die Wüste, unter glühendem Himmel ohne einen Lufthauch, als wäre die ganze Natur erstarrt – groβartig und deprimierend. Es schien, als wiche der Horizont beständig vor ihnen zurück, so wie er vor Georg von Speyer, Nikolaus Federmann und Philipp von Hutten und deren Landsknechten zurückgewichen sein musste, als sie Mitte des 16. Jahrhunderts für das Augsburger Bank- und Handelshaus der Welser, Statthalter von Venezuela, die Llanos durchquerten, um jenseits des Río Apure und anderer Flüsse einem Hirngespinst nachzujagen, nämlich Eldorado im reichen Land der Omagua zu suchen. Einige Jahre darauf machten sich Pedro de Ursúa und Lope de Aguirre mit ihren Spaniern und Indios von Peru auf den Weg, das sagenhafte Reich der Omagua zu erreichen, das Timbuktu des neuen Kontinents, wie Humboldt es nannte, fuhren den Amazonas hinunter und erreichten bloβ, sich gegenseitig zu zerfleischen. Humboldt und Bonpland fuhren den Apure zu Beginn der Regenzeit hinunter, in einer Piroge mit vier indianischen Ruderern plus Steuermann und einer kleinen palmblattgedeckten Hütte am Heck, hier und da waren die Ufer bewaldet, Tapire, Wasserschweine und der Jaguar kamen zum Saufen an den Fluss, auf dem Sand lagen regungslos Krokodile, Vögel mit buntem Gefieder und Federbusch stolzierten am Wasser entlang, es war wie im Paradies, alles erinnerte an den Urzustand der Welt, doch Humboldt wäre nicht Humboldt gewesen, hätte er nicht genau beobachtet und erkannt, dass die Tiere einander fürchteten und mieden. Einmal ging er am Ufer auf eine Gruppe von Krokodilen zu, um sie aus der Nähe zu beobachten, da stieβ er auf die frische Fährte eines Jaguars, die in Richtung Wald wies, und sah das prächtige Kätzchen 80 Schritt entfernt im Gebüsch liegen. Er erschrak, tat aber doch, was die Indios für solche Fälle geraten hatten: weitergehen, ohne zu laufen, die Arme möglichst nicht bewegen. Dann kehrte er scheinbar ruhig zurück, spazierte vor den Augen der Bestie am Wasser entlang und widerstand eine Zeitlang der Versuchung, sich umzusehen. Manchmal ist das Paradies die Hölle.