King John II had put Pêro da Covilhã in charge of diverse private missions, and finally, to use his knowledge of different languages, orders him and Afonso de Paiva to undertake a mission of exploration in the Near East and the adjoining regions of Asia and Africa, with the special assignment to learn where cinnamon and other spices can be found, as well as of discovering the land of legendary Prester John, by overland routes.

Bartolomeu Dias, at the same time, goes out to by sea find the Prester's country, as well as the termination of the African continent and the ocean route to India.

The expedition starts at Santarém, on May 7, 1487.

Covilhã and Paiva are provided with a letter of credence for all the countries of the world and with a map for navigating, taken from the map of the world and compiled by Bishop Diogo, and doctors Rodrigo and Moisés.

The first two of these were prominent members of the commission that had advised the Portuguese government to reject the proposals of Christopher Columbus.

The explorers start from Santarém and travel by Barcelona to Naples, where their bills of exchange are paid by the sons of Cosimo de' Medici; from here they go to Rhodes, where they stay with two other Portuguese, and so to Alexandria and Cairo, where they pose as merchants.

In company with Arabs from Fez and Tlemcen, they now go by way of El-Tor in the southern Sinai Peninsula to the port of Suakin on the west coast of the Red Sea, then cross to Aden, where, as it is now the monsoon, the two expedition leaders part.

Covilhã proceeds to India and Paiva to Ethiopia.

They agree to meet again in Cairo.