Κατά το διάστημα που μεσολάβησε από τη θριαμβευτική επιστροφή του Βαρθολομαίου Ντιάζ στην Πορτογαλία (1488) μέχρι την υπογραφή της Ντιάζ , με εντολή να φτάσει στις Ινδίες και να αναφέρει κατά την επιστροφή του τι βρήκε. Ταυτόχρονα, ένας σύντροφός του στάλθηκε να ταξιδέψει στην Αφρική σε αναζήτηση του Πρέστερ Τζον και του χριστιανικού του βασιλείου.

Ο Κοβίλια έφερε σε πέρας την αποστολή του εμφανιζόμενος ως Άραβας έμπορος, ταξιδεύοντας με ένα καραβάνι από το Κάιρο στο Άντεν, στο στόμιο της Ερυθράς Θάλασσας, και από εκεί με πλοίο στο ινδικό λιμάνι του Καλικούτ . Φτάνοντας στις Ινδίες περιηγήθηκε την ακτή, εξακολουθώντας να εμφανίζεται ως Άραβας και σταματώντας στα λιμάνια που συναντούσε στη διαδρομή του. Κατόπιν, πέρασε από τον Ινδικό ωκεανό με καΐκι στην ανατολική Αφρική και έπλευσε προς το νότο επισκεπτόμενος τις ισλαμικές εμπορικές πόλεις της ακτής. Έχοντας συγκεντρώσει πλούσιες πληροφορίες, επέστρεψε κατόπιν στο Κάιρο για να συναντήσει τον σύντροφό του και τους απεσταλμένους του βασιλιά.

Τα νέα που έμαθε εκεί δεν ήταν ευχάριστα. Πληροφορήθηκε ότι ο συνάδελφός του εξερευνητής ήταν νεκρός και έτσι έπρεπε να αναλάβει αυτός το καθήκον της ανεύρεσης του Πρέστερ Τζον. Παρά τις ταλαιπωρίες του, ο Κοβίλια πήρε και πάλι το δρόμο προς το νότο. Έφτασε στην Αιθιοπία, όπου και παρέμεινε, φιλοξενούμενος ή, ίσως, και αιχμάλωτος του χριστιανού ηγεμόνα της χώρας. Τριάντα χρόνια αργότερα, τον βρήκαν εκεί μέλη μιας πορτογαλικής αποστολής, αλλά ήταν πια γέρος και προτίμησε να παραμείνει παρά να επιστρέψει στην Πορτογαλία.