In 1297, with the reconquista completed, king Dinis of Portugal took personal interest in exports and in 1317 he made an agreement with Genoese merchant sailor Manuel Pessanha (Pesagno), appointing him first Admiral of the Portuguese navy, with the goal of defending the country against Muslim pirate raids. Outbreaks of bubonic plague led to severe depopulation in the second half of the 14th century: only the sea offered alternatives, with most population settling in fishing and trading coastal areas. Between 1325–1357 Afonso IV of Portugal encouraged maritime commerce and ordered the first explorations. The Canary Islands, already known to Genoese, were claimed as officially discovered under patronage of the Portuguese but in 1344 Castile disputed them, expanding their rivalry into the sea. In 1415, Ceuta was occupied by the Portuguese aiming to control navigation of the African coast. Young prince Henry the Navigator was there and became aware of profit possibilities in the Trans-Saharan trade routes. For centuries slave and gold trade routes linking West Africa with the Mediterranean passed over the Western Sahara Desert, controlled by hostile Muslim states of North Africa.
Henry wished to know how far Muslim territories in Africa extended, hoping to bypass it and trade directly with West Africa by sea, find allies in legendary Christian lands to the south like the long-lost Christian kingdom of Prester John and to probe whether it was possible to reach the Indies by sea, the source of the lucrative spice trade. He invested in sponsoring voyages down the coast of Mauritania, gathering a group of merchants, shipowners and stakeholders interested in new sea lanes. Soon the Atlantic islands of Madeira (1419) and Azores (1427) were reached.
At the time, Europeans did not know what lay beyond Cape Non (Cape Chaunar) on the African coast, and whether it was possible to return once it was crossed. Nautical myths warned of oceanic monsters or an edge of the world, but Prince Henry's navigation challenged such beliefs: starting in 1421, systematic sailing overcame it, reaching the difficult Cape Bojador that in 1434 one of Prince Henry's captains, Gil Eanes, finally passed.
A major advance was the introduction of the caravel in the mid-15th century, a small ship able to sail windward more than any other in Europe at the time. Evolved from fishing ships designs, they were the first that could leave the coastal cabotage navigation and sail safely on the open Atlantic. For celestial navigation Portuguese used ephemeris, which have experienced a remarkable diffusion in the 15th century. These tables revolutionized navigation, allowing to calculate latitude. Exact longitude, however, remained elusive, and mariners struggled to determine it for centuries. Using the caravel, systematic exploration continued ever more southerly, advancing on average one degree a year. Senegal and Cape Verde Peninsula were reached in 1445 and in 1446, António Fernandes pushed on almost as far as present-day Sierra Leone.
In 1453 the fall of Constantinople to the hands of the Ottomans was a blow to Christianity and the established business relations linking with the east. In 1455 Pope Nicholas V issued the bull Romanus Pontifex reinforcing previous Dum Diversas (1452), granting all lands and seas discovered beyond Cape Bojador to the King of Portugal and his successors, as well as trade and conquest against Muslims and pagans, initiating a mare clausum policy in the Atlantic.
In 1456 Diogo Gomes reached the Cape Verde archipelago. In the next decade several captains at the service of Prince Henry - including the Genoese Antonio da Noli and Venetian Alvise Cadamosto - discovered the remaining islands which were occupied still during the 15th century. The Gulf of Guinea would be reached in the 1460s's.