Covilham, or Covillan, was born in a town of that name in Portugal, and went, when a boy, into Castile, where he entered the service of Don Alphonso, duke of Seville. On a war breaking out between Portugal and Castile, he returned into his native country, where he got into the household of King Alphonso, who made him a man-at-arms. After the death of that king, he was one of the guard of King John, who employed him on a mission into Spain, on account of his knowledge in the language. He was afterwards employed in Barbary, where he remained some time, and acquired the Arabic language, and was employed to negotiate a peace with the king of Tremesen. He was a second time sent into Barbary on a mission to King Amoli-bela-gegi, to procure restitution of the bones of the infant Don Fernando, in which he was successful.
After his return, he was joined in commission, as before-mentioned, with Alphonso de Payva, and these adventurous travellers left Lisbon in May 1487. Covilham was furnished with a very curious map for these times, by the Prince Emanuel, afterwards king of Portugal, which had been copied and composed, with great care and secrecy, by the licentiate Calzadilla, afterwards bishop of Viseo, assisted by Doctor Rodrigo, and a Jewish physician named Moses; which map asserted the practicability of passing by sea to India round the southern extremity of Africa, on some obscure information which had been collected by those who constructed it.
With a supply of 500 crowns in money, and a letter of credit, or bills of exchange, Covilham and De Payva went first to Naples, where their bills of exchange were paid by the son of Cosmo de Medici. From Naples they went by sea to the island of Rhodes, and thence to Alexandria in Egypt, whence they travelled as merchants to Grande Cairo, and proceeded with the caravan to Tor on the Red Sea, near the foot of Mount Sinai. They here received some information respecting the trade which then subsisted between Egypt and Calicut, and sailed from that place to Aden, a trading city of Yemen, on the outside of the Straits of Babelmandeb. The travellers here separated; Covilham embarking in one vessel for India, while De Payva took his passage in another vessel bound for Suakem on the Abyssinian coast of the Red Sea, having engaged to rejoin each other at Cairo, after having carried the directions of their sovereign into effect.