An der Spitze der Flotte steht König Johann, ihm zur Seite sein Sohn Heinrich. Widrige Winde und fehlende Erfahrung in der Seekriegsführung halten die Schiffe bis zum 21. August auf dem Meer, dann ist Ceuta in 13 Stunden erobert. Überschießendes Temperament, jähwütiges Voranstürmen, Massaker an Gefangenen, Frauen und Kindern. Der Prinz kennt kein Zurück und kein Pardon.

Pedro de Meneses, zum Gouverneur der Stadt und Garnison Ceuta ernannt, wird rasch mit Lösegeldern für gefangene Mauren reich, auch profitiert er von den Beutezügen der Piraten, die unter seinem Schutz auf Kaperfahrt gehen; bald steht Heinrich bei ihm tief in der Kreide. Die Hafenstadt indes, durch bitterfeindliches Hinterland nun isoliert, ist kein maurischer Handelsplatz, kein Karawanenziel mehr, muss über See ernährt werden. Der große Beutezug war ein Fehlschlag, schon werden in Portugal Sondersteuern erhoben, die höchsten natürlich von den jüdischen Gemeinden, sogar der Papst soll helfen.

Heinrich wird mit Titeln und Ämtern beladen: Herzog von Viseu, Gouverneur der Algarve (mit dem Monopol auf den Thunfischfang) und Großmeister des Christusordens. Dieser Orden ist ein Nachfolger des untergegangenen Templerordens; in Portugal hat er sich das Templer-Vermögen bewahren können. Der Zugriff auf die Revenuen gibt Heinrich Handlungsfreiheit, dafür räumt er dem Christusorden später die geistliche Vormachtstellung in allen überseeischen Gebieten ein und gelobt ein Leben in Keuschheit. Tatsächlich wird niemals von einer Frau an seinem Hofe berichtet, stattdessen tummeln sich dort ehrgeizige junge Männer. Unter ihnen findet er genug, die er zur Erkundung der unbekannten Küsten Westafrikas südlich der maurischen Stützpunkte ausschickt.

Jenseits des Kaps Bojador (26° 7' N), des "Kaps ohne Wiederkehr", liegt das mar tenebroso, das Meer der Finsternis. Hier, so heißt es, ist jede Seefahrt unmöglich: Das Wasser nur roter Schlamm mit Ungeheuern darin, die Ufer ächzen unter einer glühenden Sonne, die alle Menschen schwarz färbt. Hier liegt auch der Magnetberg, der alles Eisen aus den Schiffen zieht, und hier gibt es die Strudel, die sie in den Abgrund reißen.

Und doch muss es da noch weitergehen. Denn irgendwo hinter den Ländern der Heidenschaft, so wollen es fromme Legenden, liegt das christliche Reich des sagenhaften Erzpriesters Johannes. Im Nordosten Chinas, meinte Marco Polo, Heinrich aber vermutet es im östlichen Afrika, bei den Quellen des Nils. In diesem Reich soll es gehörnte Menschen geben, Hundsköpfige, Einäugige, Giganten, Vampire und den Vogel Phönix. Die Wasser dort können das Leben verlängern, die Flusskiesel seien Juwelen, an Gold herrsche kein Mangel. 72 Könige sind dem Erzpriester untertan, mit riesigen Armeen – kurz: Er muss gefunden, muss Kampfgenosse werden gegen den Islam. Ein großer Fluss aus dem Inneren Afrikas wird zu ihm führen.

Heinrich chartert, kauft Karavellen, stellt seine abergläubischen Algarvefischer unter das Kommando junger Herren seines Hofstaats. Nach einem guten Dutzend Fehlschlägen kehrt 1434 einer von ihnen, Gil Eanes, zurück: Jenseits des fürchterlichen Kaps sehe es nicht anders aus als nördlich von ihm.

Der Prinz ist da schon Herr auf Madeira, das 1418 erreicht und zügig durch ihn besiedelt wird, auch mit Bauern aus Deutschland. Vorzügliches Langholz gibt es dort und "Drachenblut" – das Baumharz ist ein kostbares Heil- und Färbemittel –, auf Rodungen gedeiht Zuckerrohr.

Heinrichs Kundschafter sollen nicht mit leeren Laderäumen heimsegeln. Als sein Knappe Afonso de Baldaia 1436 zurückkehrt, hat er Robbenfelle geladen und Robbenfett für die Seifensieder. Wie beim Thunfischfang hält der Prinz auch das Monopol über Portugals Seifenherstellung und -handel.