La primera noticia que se tiene de él (anterior a 1445) fue como prisionero de los piratas berberiscos en el Mediterráneo occidental; durante el presidio adquirió conocimientos de árabe y probablemente concibió la exploración del interior de África, un continente cuyas costas los portugueses estaban en ese momento comenzando a explorar.
En 1445 se instaló voluntariamente en Guinea y recabó y envió toda la información que pudo al príncipe Enrique el Navegante. Con este motivo acompañó a Antão Gonçalves a Rio d'Ouro (Río de Oro), donde desembarcó y se adentró en el interior del país con algunos pastores nativos. Estuvo siete meses y de nuevo fue llevado aguas adentro por Gonçalves al punto más al sur conocido, cerca del cabo Ransom (cabo Mirik o Timiris, actual Mauritania).
Sus relatos de sus experiencias resultaron ser de gran interés y valor, no solo por las características naturales, clima, fauna y flora del suroeste del Sáhara, sino también por las afinidades raciales, lenguaje, escritura, religión, hábitos nómadas y comercio de sus habitantes. Estos mantenían un cierto comercio de esclavos, oro, etc. con los países berberiscos (especialmente con Túnez), y los clasificó como «árabes», «bereberes» y los «Tawny Moors», que no hablaban ni escribían en árabe.
En 1446 y 1447 Fernandes participó en otras expediciones a Río de Oro y otras partes del África occidental al servicio del príncipe Enrique. Conoció personalmente a Gomes Eannes de Azurara, el historiador de este temprano periodo de la expansión portuguesa, y por la forma en que se refiere a él Azurarase, se deduce que los descubrimientos de Fernandes de tierras y razas desconocidas eran apreciados totalmente en su país.
