Проинструктированные португальскими космографами, снабжённые необходимой информацией и деньгами, Ковильян и Афонсу де Паива под видом торговцев 14 июня 1487 отплыли из Барселоны. В Александрии (Египет) путешественники закупили товары для поддержания имиджа торговцев и, присоединившись к торговому каравану, пересекли пустыню и достигли восточного берега Красного моря. Затем в течение длительного времени путешествовали по Аравии, были в Медине и Мекке, где выдавали себя за мусульман, достигнув Адена и портов на побережье Индийского океана.
В 1488 г. в Адене они разделились: Афонсу де Пайва отбыл в Абиссинию (Эфиопию) на поиски государства Пресвитера Иоанна, а Ковильян в сопровождении нескольких мавров отплыл в сторону Индии, посетив Суэц (Торо), Аден, Ормуз, Гоа, Каликут и Софальский берег в Мозамбике. Они договорились встретиться в Каире.
Путь торговцев специями (зеленая линия) и маршруты Васко да Гама (черная), Перу да Ковильян (оранжевая) и Афонсу де Паива (синяя)
Афонсу де Паива прибыл в Суакин, где надеялся присоединиться к каравану к месту назначения. Дальнейшие подробности его жизни отсутствуют.
30 января 1491 Ковильян прибыл в Каир для встречи А. де Паивой, но, по слухам, тот умер от чумы за неделю до его приезда, не оставив никакой информации о результатах своей миссии.
По возвращении в Каир в 1490 году Ковильян узнал о смерти Паивы в Эфиопии.
Улица в Лиссабоне, названная в честь Афонсу де Паива
Джеймс Брюс пишет: «Афонсу де Паива, пытаясь осуществить поездку таким образом, пропал без вести, и слухов о нём больше не было».
John Jeremy Hespeler-Boultbee, Richard Pankhurst. A Story in Stones: Portugal’s Influence on Culture and Architecture in the Highlands of Ethiopia 1493—1634, CCB Publishing, 2006, ISBN 0978116216 (англ.)
