彼が最初に文献に登場するのは、西地中海でムーア人を捕らえたことを記録したことによってである。彼はこの時期にアラビア語の知識を身につけた。当時ポルトガル人が西アフリカの海岸部を探検し始めていたが、彼はアフリカ内陸部の未知の地域の探検を計画していた可能性もある。
1445年、彼は歴史の表舞台に現れる。彼は航海先のギニアに残ることを志願し、エンリケ航海王子に報告するために現地の情報を集めた。彼はアンタン・ゴンサルヴェス（Antão Gonçalves）とともに「金の川」（リオ・デ・オロ Rio do Ouro、現在の Río de Oro 、西サハラ南部の海岸部）へ向かい、上陸して先住民の羊飼いたち数人とともに内陸へ向かった。このゴンザルヴェスという人物は1441年にヌーノ・トリスタン（Nuno Tristão）とともに西サハラを探検し、その際狩ったチチュウカイモンクアザラシを運ぶためにベルベル人から黒人奴隷を買い、ポルトガルの黒人奴隷貿易のさきがけとなった人物であった。フェルナンデスは7ヶ月とどまり、ゴンザルヴェスとともに「身代金岬」（Cape of Ransom、Cape Mirik）近くで海岸に戻った。彼のもたらした報告と経験には大きな利益と価値があった。報告は南西サハラの自然環境、気候、動物相、植物相にとどまらず、民族の区分、言語、文字、宗教、遊牧民の習慣、奴隷の交易にも及んだ。遊牧民たちは南西サハラと北アフリカ（当時バーバリー・コーストと呼ばれたモロッコからリビアにかけての海岸部、特にチュニス）との間でキャラバンによって金や黒人奴隷を貿易し、この地域の民族はアラブ人、ベルベル人、そしてアラビア語を解さない「褐色のムーア人」と呼ばれる人々に区分されていた。
1446年と1447年、フェルナンデスはリオ・デ・オロへの再度の探検に向かい、西アフリカの他の地域についてエンリケに報告した。彼は、有名な年代記作家でポルトガル海外進出時の歴史を綴った人物であるゴメス・エアネス・デ・アズララ（Gomes Eannes de Azurara）と個人的な知り合いで、アズララの言葉によってフェルナンデスによる知られざる土地や民族の探検記録は本国で受け容れられた[1]。
