Hij was een telg uit een gegoede familie uit Castelo Branco. Hij erfde het ambt van belastingambtenaar in zijn geboorteplaats en werd koninklijke schrijver voor de Hebreeuwse gemeenschap. In die functie leerde hij de Hebreeuwse en Arabische taal. Hij werd opgemerkt door de koning tijdens de Slag bij Toro in 1476.
Dankzij zijn kennis van de oosterse talen en zijn contacten in het Midden-Oosten werd hij samen uitgestuurd met Pêro da Covilhã om het rijk van Pape Jan te vinden. De route werd uitgestippeld door de kosmografen van het hof. Terzelfder tijd werd Bartolomeu Dias uitgestuurd om de contouren van Afrika te verkennen en een weg naar India te vinden.
Da Covilhã en De Paiva vertrokken op 7 mei 1487 vanuit Santarém en reisden via Barcelona en Napels naar Rhodos. Van de Tempelridders daar kregen ze het advies om zich voor te doen als islamitische handelaren in honing. In deze vermomming reisden Da Covilhã en De Paiva naar Alexandrië. In het gezelschap van Moorse kooplieden uit Fez trokken ze verder naar Caïro en Aden aan het begin van de Rode Zee. Daar scheidden hun wegen. De Paiva ging naar Abessinië, terwijl da Covilhã verder reisde naar India. Ze spraken af elkaar in Caïro weer te treffen.
Eind 1490, begin 1491 keerde Da Covilhã terug in Caïro. Hij trof daar twee joodse afgezanten van João II, een rabbijn en een schoenmaker. Zij vertelden hem dat de Paiva na terugkeer in Caïro was gestorven zonder dat hij verslag van zijn reis had kunnen doen. Na het schrijven van zijn verslag, vertrok Da Covilhã naar Abessinië om de missie van Afonso de Paiva af te maken. Da Covilhã zou de rest van zijn leven gedwongen in Abessinië blijven en zou Portugal nooit terugzien.
