Afonso de Paiva e Pêro da Covilhã em demanda de Preste João

Nem só a viagem marítima da descoberta, era o objectivo nacional. As viagens e a aventura era o meio para atingir outros fins uma deles a Índia, outro a exploração dessas novas terras de gente negra chamada África.

Nessa África enorme, havia o aliciante de descobrir o Reino do Preste João, cujas primeiras notícias chegaram à Europa em 1145, quando Hugo de Gebel, Bispo de uma colónia cristã no Líbano, informou o Papa da existência de um reino cristão situado "para lá da Pérsia e da Arménia", governado por um rei-sacerdote, que seria descendente de um dos Reis Magos.

Foi esse desafio que D.João II iniciou, quando convocou Pêro da Covilhã e Afonso de Paiva,para encontrar esse Reino africano cristão.

Munidos das melhores cartas Mapa Mundi, que na época se podiam desenhar servindo-lhes de guia, cartas e crédito e várias oferendas, se fizerem à vida, no que seriam fundamentalmente um trabalho de exploração e de cautelosa espionagem, pelo que partiram discretamente de Santarém a 8 de Maio de 1487.

Entraram em África por Alexandria já disfarçados de mercadores, numa aventura também perigosa mas que no imediato e durante muitos anos não se soube nada desses dois espiões, em Portugal.