Era necesario el conocimiento del mercado oriental de las especias y un contacto directo con los países de origen por lo que con mucho cuidado y secreto preparó una nueva expedición en la que participaron dos hombres de la confianza del rey y conocedores de la lengua árabe, Afonso de Paiva, de Castelo Branco, y Pêro da Covilhã o Covilhao.